[ZOJ 4062][2018ICPC青岛站][Plants vs. Zombies]

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4062

题目大意:给一个大小为n的数组,数组编号从1到n,每一个元素的值代表每经过一次这个位置,这个位置就加上这个元素的值,所有位置最初的值都是0,最初从0开始移动m次,求最终所有位置的最小值的最大值是多少.(n<1e5,m<1e12,a[i]<1e5)

题解:二分+贪心,每个位置尽量往右弹跳(因为之前的位置都满足了条件,只需要尽可能让右边的大即可.),注意各种细节即可.

(1)int/int的时候向0取整,而不是向下取整(所以要小心负数/正数的情况)

(2)要避免乘法爆long long ,比如对于先乘后除的式子先除后乘,同时当sum>m时直接return false,避免继续加下去爆long long (现场赛也是因为这个地方爆long long 没有了牌子..)

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<map>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 ll n,m;

 ll a[];

 bool check(ll x){

     ll sum=;

     ll res=;

     for(int i=;i<n;i++){

         ll xx=(x/a[i]+(x%a[i]!=)-res);

         if((x/a[i])+(x%a[i]!=)<=res){if(i!=n-)xx=;else xx=;}

         res=xx-;

         if(res<)res=;

         sum+=xx+res;

         if(sum>m)return false;

     }

     return true;

 }

 int main(){

     int t;

     cin>>t;

     while(t--){

         scanf("%lld%lld",&n,&m);

         ll maxx=;

         for(int i=;i<n;i++){

             scanf("%lld",&a[i]);

             maxx=max(maxx,a[i]);

         }

         ll r=1e18;

         ll l=;

         ll ans=;

         while(l<=r)

         {

             ll mid=(l+r)>>;

             if(check(mid))

             {

                 ans=mid;

                 l=mid+;

             }else{

                 r=mid-;

             }

         }

        printf("%lld\n",ans);

     }

     return ;

 }