【BZOJ】2016: [Usaco2010]Chocolate Eating(二分)
2024-10-14 02:17:44
http://www.lydsy.com/JudgeOnline/problem.php?id=2016
这些最大最小显然是二分。
但是二分细节挺多的。。。这里注意二分的区间,可以累计所有的可能,然后这就是二分区间的右界。。(我是sb)
然后二分的时候,判断那里一定要仔细啊。。
还有这题要开longlong啊(雾)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }
#define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } typedef long long ll;
const int N=50005;
ll a[N];
int n, d;
bool check(ll x) {
ll sum=0; int tot=1;
for1(i, 1, n) {
sum+=a[i];
while(tot<=d && sum>=x) sum>>=1, ++tot;
if(tot>d) return 1;
}
return 0;
}
void pri(ll x) {
ll sum=0; int tot=1;
for1(i, 1, n) {
sum+=a[i]; printf("%d\n", tot);
while(tot<d && sum>=x) sum>>=1, ++tot;
}
} int main() {
read(n); read(d);
ll l=0, r=0;
for1(i, 1, n) read(a[i]), r+=a[i];
while(l<=r) {
ll m=(l+r)>>1;
if(check(m)) l=m+1;
else r=m-1;
}
printf("%lld\n", l-1);
pri(l-1);
return 0;
}
Description
贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完,而是打算制定一个计划,
使得在接下来的D天里,她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量,一开始的时候是0,当她每天晚上睡觉的时候,快乐指数会减半(奇数时向下取整)。贝西把她的巧克力按照收到的时间排序,并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候,她的快乐指数会增加Hj。每天可以吃任意多块巧克力,如何帮助贝西合理安排,使得D天内她的最小快乐指数最大呢?
举个例子:假设一共有五块巧克力,贝西打算在五天时间内将它们吃完,每块巧克力提
供的快乐指数分别为10,40,13,22,7。则最好的方案如F:
起床时快乐指数 |
就寝时快乐指数 |
0 |
50 |
五天内的最小快乐指数为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
10
40
13
22
7
Sample Output
24
1
1
3
4
5
1
1
3
4
5
HINT
Source
最新文章
- 「Ionic」創建新項目
- type parameters of <;T>;T cannot be determined; no unique maximal instance exists for type variable T with upper bounds int,java.lang.Object
- swift 2.x学习笔记(二)
- static NSString *ID的改进
- 用ActionSupport实现验证
- HDU4289Control(最大流)
- apache用户认证、默认主机、301跳转
- CSDN头版头条 《近匠》 Wijmo 5 CTO:从Web到移动,我的25年编程生涯
- Extension+NVelocity
- CentOS裸机环境下安装php-7.3.1
- JS中----this的指向和如何修改this的指向
- 重开Vue2.0
- 浮动布局float
- ";=="; equals和hashCode的联系和区别
- mysql 数据类型 目录
- Python-sys模块,异常
- Week5——applet
- UEditor自定义toolbar工具条
- scrollbar样式
- sql server中字符串无法替换空格的问题
热门文章
- PHPMailer_v5.1 使用[转]
- Php取扩展名
- react 设置代理(proxy) 实现跨域请求
- linux svn恢复删除的文件夹和文件(转)
- 機器學習基石(Machine Learning Foundations) 机器学习基石 作业三 课后习题解答
- jenkins部署前端node项目实例
- 安装python3.6后使用pip报错
- java.lang.NullPointerException org.apache.jsp.index_jsp._jspInit(index_jsp.java:22)
- 【转】C# 视频监控系列(12):H264播放器——播放录像文件
- python selenium --调用js