「BZOJ2016」[Usaco2010] Chocolate Eating
Description
贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完，而是打算制定一个计划，
使得在接下来的D天里，她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量，一开始的时候是0，当她每天晚上睡觉的时候，快乐指数会减半（奇数时向下取整）。贝西把她的巧克力按照收到的时间排序，并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候，她的快乐指数会增加Hj。每天可以吃任意多块巧克力，如何帮助贝西合理安排，使得D天内她的最小快乐指数最大呢？
举个例子：假设一共有五块巧克力，贝西打算在五天时间内将它们吃完，每块巧克力提
供的快乐指数分别为10，40，13，22，7。则最好的方案如F：
| 天数 | 起床时快乐指数 | 食用的巧克力 | 就寝时快乐指数 |
| 1 2 3 4 5 |
0 25 12 12 17 |
10+ 40
13 |
50 25 25 34 24 |
五天内的最小快乐指数为24，这是所有吃法中的最大值。
Input
第一行：两个用空格分开的整数：N和D，1≤N．D≤50000
第二行到第N+1行：第1+1行表示第i块巧克力提供的快乐指数Hj，1≤Hi≤1000000
Output
第一行：单个整数，表示贝西在接下来D天内的最小快乐指数的最大值
第二行到第N+1:在第i+l行有一个整数，代表贝西应该在哪一天吃掉第i块巧克力。
如果有多种吃法，则输出按照词典序排序后最靠后的方案
Sample Input
55
10
40
13
22
7
Sample Output
24
1
1
3
4
5
题解
二分+判定答案。。。
注意剩下的巧克力应该在最后一天吃掉
|
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 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<set> #include<queue> #include<map> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll 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; } ll l,r,ans; int n,d; int h[50005],a[50005]; bool jud(ll x,bool f) { ll tmp=0; int now=1; for(int i=1;i<=d;i++) { tmp>>=1; while(now<=n&&tmp<x) { tmp+=h[now]; if(f)a[now]=i; now++; } if(tmp<x)return 0; } if(f)for(int i=now+1;i<=n;i++)a[now]=d; return 1; } int main() { n=read();d=read(); for(int i=1;i<=n;i++) h[i]=read(),r+=h[i]; while(l<=r) { ll mid=(l+r)>>1; if(jud(mid,0)) { ans=mid; l=mid+1; } else r=mid-1; } printf("%lld\n",ans); jud(ans,1); for(int i=1;i<=n;i++) if(!a[i])printf("%d\n",d); else printf("%d\n",a[i]); return 0; } |
计数器 9859960
OI 课件=>
OI 课件=>
其实最后输出答案的时候不用判断
在Judge里面，if(f)for(int i=now+1;i<=n;i++)a[now]=d;
这句应该是 if(f) for (int i = now; i <= n; i++) a[now] = d;