抄書

題目大意：

有n本書，分給m個(gè)人抄，每個(gè)人只能拿到連續(xù)的書（不能把一本書分開），問抄書最多的人要抄多少頁

樣例輸入

9 3

100 200 300 400 500 600 700 800 900

樣例輸出

1700

數(shù)據(jù)范圍限制

對(duì)于10%的數(shù)據(jù),有N<=10

對(duì)于50%的數(shù)據(jù),有N<=500;

對(duì)于100%的數(shù)據(jù),有N<=3000;

解題思路：

這道題很可能想到DP但會(huì)炸，我們要用二分枚舉答案，然后用一沖循環(huán)來把書分配給每個(gè)人

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,m,num,maxn,l,r,mid,p,w,b[3005],a[3004]; int main() {scanf("%d %d",&n,&m);for (int i=1;i<=n;i++){scanf("%d",&a[i]);maxn+=a[i];//求總值num=max(num,a[i]);//求最大的}l=num;//最小的r=maxn;//最大的while(l<=r){mid=(l+r)/2;//二分p=1;memset(b,0,sizeof(b));//清零w=1;for (int i=1;i<=n;i++)if (b[w]+a[i]<=mid) b[w]+=a[i];//沒有大于當(dāng)前枚舉的結(jié)果else {if (w==m)//若沒人了，就是沒有解{p=0;break;}b[++w]+=a[i];//有人就換一個(gè)人}if (p) r=mid-1;//二分else l=mid+1;//二分}printf("%d",l);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【二分】抄书 （jzoj 2123）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。