[CodeVS 3168]抄书问题 3

danihao123 posted @ 2016年8月06日 17:40 in 题解 with tags CodeVS 二分答案 贪心 , 115 阅读
转载请注明出处:http://danihao123.is-programmer.com/

二分答案处女作,嗯……

这题没啥好说的……二分答案+贪心判定。注意最后输出的时候不能一味贪心,否则区间数可能小于k!

代码:

#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1000001;
int n;
ll A[maxn];
bool hf(int k,int x){
    register int i,d=1;
    register ll ans=0;
    for(i=1;i<=n;i++){
        if(ans+A[i]>x){
            d++;
            ans=A[i];
        }else{
            ans+=A[i];
        }
    }
    return d<=k;
}
vector<pii> as;
void print(int k,int x){
    register int i,kr=k,l=n,r=n;
    register ll cnt=0;
    for(i=n;i>=1;i--){
        if(cnt+A[i]>x || i<kr){
            l=i+1;
            kr--;
            as.push_back(make_pair(l,r));
            cnt=A[i];
            l=i;
            r=i;
        }else{
            l=i;
            cnt+=A[i];
        }
    }
    as.push_back(make_pair(l,r));
    for(i=as.size()-1;i>=0;i--)
        printf("%d %d\n",as[i].first,as[i].second);
}
int main(){
    register int i,k;
    register ll L=-1,R=0,M;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        R+=A[i];
        L=max(L,A[i]);
    }
    if(R<=1)
        R=2;
    while(R>L){
        M=L+(R-L)/2;
        if(hf(k,M))
            R=M;
        else
            L=M+1;
    }
    print(k,L);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter