解题报告 loongint 的存款

1.        题目

Loongint的存款

Description

Loongint希望你能帮他规划一下今年一年的收入和支出。对于每一个月,Loongint可以选择打工挣钱或者陪MM去消费,每个月挣的钱(s)和消费的钱(d)的数额都是一定的。可是,LoongintMM不希望Loongint有结余,因为这样Loongint可能去找别的MM。可是作为一个顶天立地的男人JLoongint非常渴望能结余。

MM只能查Loongint任意连续五个月的经济情况,所以Loongint必须让任意连续五个月的收入都是负的(也就是五个月的总支出大于总收入)。求年终Loongint能结余么?如果能,输出最大结余,如果不能,输出No Save

Input

第一行n表示有n组测试数据。

接下来n行,每行有sd

Output

n行,每行输出一年的最大结余或者No Save

Sample Input

2

1 1

14 6

Sample Output

0

No Save

Hint

对于30%的数据,1=<n<=100

对于100%的数据,1<=n<=100000sd和最后的解都属于Longint

2.        算法

首先计算出来在五个月中,总数是负数的情况下,怎么样才能达到最大值,以及最大值是多少。

然后,保证每五个月都满足这个条件,并且尽量在前几个月赚钱。

比如说五个月中,赚三个月钱,花两个月,可以得到负数的最大值,那么,则在前五个月中,前三个月赚钱,后两个月花。则,对于第六个月来说,以他为结尾的五个月( 2,3,4,5,6 月)中, 2,3 月赚钱, 4,,5 月花,为了满足条件,所以这个月得赚钱。。。。。。然后依次类推。

3.        注意事项

本题很语文,要注意读题。

4.        代码

贪心 (SueMiller)

var n:longint;

    s,d,i,j,k,temp,ss,dd:longint;

    v:array[0..12]of integer;

 

begin

  assign(input,'save.in');reset(input);

  assign(output,'save.out');rewrite(output);

 

  readln(n);

  for i:=1 to n do

    begin

      readln(s,d);

 

      temp:=-maxlongint;

      k:=0;

      for j:=1 to 5 do

        begin

          if (j*s-(5-j)*d>temp) and (j*s-(5-j)*d<0) then

            begin

              temp:=j*s-(4-j)*d;

              k:=j;

            end;

        end;

 

      ss:=k;dd:=5-k;

      fillchar(v,sizeof(v),0);

      for j:=1 to k do

        v[j]:=1;

 

      for j:=6 to 12 do

        begin

          v[j]:=k-v[j-4]-v[j-3]-v[j-2]-v[j-1];

          if v[j]=0 then inc(dd) else inc(ss);

        end;

 

      if ss*s-dd*d>=0 then writeln(ss*s-dd*d)

      else writeln('No Save');

    end;

 

  close(input);close(output);

end.

 

 

原文地址:https://www.cnblogs.com/SueMiller/p/2213109.html