刷题与ZZ错误记录15

CodeForces-551C GukiZ hates Boxes

题面

【VJudge】 【CodeForces】

一条直线上 有n堆盒子, 第i堆盒子有ai个盒子
有m个学生要去移走所有的盒子, m个学生是同时行动的,
一开始所有的学生站在第一堆盒子的左边,他们移动到第一堆盒子需要花费1时间
接下来每个学生都可以有两种选择
1: 移动到下一堆,花费1的时间
2: 移走当前堆的一个盒子(如果还有盒子的话), 花费1的时间
请问最少需要多少时间能移走所有的盒子
n,m <= 10^5
ai <= 10^9

总结

今天做的都是二分专题,这题也是使用二分来做,二分所用时间,但如何来检查呢?我的话就是使用一个简单的贪心:让这个人移动到距离最远的有箱子的点,然后在剩下的时间内尽可能的从后往前搬箱子。

槽点

  1. (WA) 这题需要开Long Long!

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ai[100005],aii[100005],pi[100005];
long long l,r,mid,f;
inline bool check(long long t){
    long long tot=0,pos=0,tt,ff=f;
    for(int i=1;i<=n;i++){
        aii[i]=ai[i];tot+=ai[i];
    }
    for(int j=1;j<=m;j++){
        pos=ff;tt=t;
        tt-=ff;
        while(tt){
            if(pos==0)break;
            if(aii[pos]<=tt){
                tt-=aii[pos];
                tot-=aii[pos];
                aii[pos]=0;
                pos=pi[pos];
                ff=pos;
            }else{
                aii[pos]-=tt;
                tot-=tt;
                tt=0;
            }
        }
    }
    return !tot;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&ai[i]);
        if(ai[i]){
            pi[i]=f;f=i;
        }
    }
    l=1;r=(long long)(1)<<60;
    while(l<r){
        mid = (l+r)>>1;
        if(check(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    printf("%lld\n",l);
    return 0;
}

页面: 1 2 3 4 5 6

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注