[ZOJ 4062][2018ICPC青岛站][Plants vs. Zombies]-白红宇

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

阅读量：5129 次

发布时间：2019-06-13

本文共 985 字，大约阅读时间需要 3 分钟。

题目大意:给一个大小为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 没有了牌子..)

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
          5 #include
          
            6 #include
           
             7 using namespace std; 8 typedef long long ll; 9 ll n,m;10 ll a[100005];11 bool check(ll x){12 ll sum=0;13 ll res=0;14 for(int i=0;i
            
             m)return false;21 }22 return true;23 }24 int main(){25 int t;26 cin>>t;27 while(t--){28 scanf("%lld%lld",&n,&m);29 ll maxx=0;30 for(int i=0;i
             
              >1;40 if(check(mid))41 {42 ans=mid;43 l=mid+1;44 }else{45 r=mid-1;46 }47 }48 printf("%lld\n",ans);49 }50 return 0;51 }

View Code

转载于:https://www.cnblogs.com/MekakuCityActor/p/9943659.html

你可能感兴趣的文章