1583: [Usaco2009 Mar]Moon Mooing 哞哞叫

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 244 Solved: 126
[Submit][Status][Discuss]

Description

Input

第一行两个数，C和N

第二行3个数，a1,b1,c1 第三行3个数，a2,b2,c2

Output

一个整数代表最长的那一次嚎叫

Sample Input

3 10
4 3 3
17 8 2

Sample Output

HINT

Source

Gold

题解：难以想象USACO竟然有此般水题，更何况还是GOLD DIVISION。。。（PS：但是我会告诉你我不仅仅第一反应是用堆做，而且还逗比了一次——忘开int64了TT）

其实，由于题目中说了\( d_1 \leq a_1 \)和\( d_2 \leq a_2 \)，所以满足\( \frac{a_1}{d_1} \geq 1 \)和\( \frac{a_2}{d_2} \geq 1 \),所以整个迭代式处于一个上升的阶段，也就是说问题就完全成了一个类似归并排序的东西了——直接两条线线性合并下搞定，时间复杂度\( O\left( N \right) \)

 /**************************************************************

     Problem:

     User: HansBug

     Language: Pascal

     Result: Accepted

     Time: ms

     Memory: kb

 ****************************************************************/

 var

    i,j,k,l,m,n,a1,b1,c1,a2,b2,c2,i1,i2:longint;

    x1,x2:int64;

    a:array[..] of int64;

 begin

      readln(m,n);

      readln(a1,b1,c1);

      readln(a2,b2,c2);

      a[]:=m;i:=;

      i1:=;i2:=;

      x1:=(a1*m) div c1+b1;

      x2:=(a2*m) div c2+b2;

      while i<=n do

            begin

                 if x1<x2 then

                    begin

                         if x1<>a[i-] then

                            begin

                                 a[i]:=x1;

                                 inc(i);

                            end;

                         inc(i1);

                         x1:=(a[i1]*a1) div c1+b1;

                    end

                 else

                     begin

                          if x2<>a[i-] then

                             begin

                                  a[i]:=x2;

                                  inc(i);

                             end;

                          inc(i2);

                          x2:=(a[i2]*a2) div c2+b2;

                     end;

            end;

      writeln(a[n]);

      readln;

 end.

巴特西

1583: [Usaco2009 Mar]Moon Mooing 哞哞叫

1583: [Usaco2009 Mar]Moon Mooing 哞哞叫

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章