「NOIP模拟赛」工资
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）
聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）
输入
第一行 2个数 n,m
接下来n行，每行一个数，代表Vi.
输出
最小的最大钱数。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
样例说明
100 400//300 100//500//101//400//
“//”表示老大要去拿钱。
数据范围
20% 1<=n<=20
另 20% 1<=n<=50,Vi的和不超过1000
100% 1<=n<=100,000,m<=n,Vi<=10,000
二分答案+判断。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #define inf 1000000000 inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int a[100005]; bool jud(int x) { int sum=0,tot=0; for(int i=1;i<=n;i++) { if(a[i]>x)return 0; if(sum+a[i]<=x)sum+=a[i]; else { sum=a[i];tot++; if(tot>=m)return 0; } } return 1; } int main() { //freopen("money.in","r",stdin); //freopen("money.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); int l=0,r=1000000000; while(l<=r) { int mid=(l+r)>>1; if(jud(mid)) { ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); return 0; } |
计数器 9775152
OI 课件=>
OI 课件=>
这道题能用划分型的DP吗？
可能不行