icpc:problems:luogup2985
problems | |
---|---|
名称 | Chocolate Eating S |
题目编号 | P2985 |
题目链接 | luogu.com.cn/… |
来源 | USACO |
算法分类 | 二分答案 |
难易程度 | 容易 |
Chocolate Eating S
想法
二分最差的心情,根据最差的心情检查可行性与组合答案。最后输出时需要根据二分的答案再组合一次答案,因为二分最后一次可能check的是不可行的情况。
代码实现
#include<cstdio> #include<cstring> const int N = 1e4*5 + 10; int n, d; int line[N], ans[N]; bool check(long long int x) { long long int hart = 0; int t = 0; memset(ans, 0, sizeof(ans)); for(int i=1; i<=d; i++) { hart /= 2; while(hart < x) { hart += line[++t]; ans[t] = i; if(t > n) return false; } } while(t <= n) ans[++t] = d; return true; } int main() { scanf("%d %d", &n, &d); long long int sum = 0; for(int i=1; i<=n; i++) { scanf("%d", &line[i]); sum += line[i]; } long long int l = 0, r = sum, mid; while(l < r) { mid = (l + r + 1) / 2; if(check(mid)) l = mid; else r = mid - 1; } printf("%lld\n", l); check(l); for(int i=1; i<=n; i++) { printf("%d\n", ans[i]); } return 0; }
/app/www/public/data/pages/icpc/problems/luogup2985.txt · 最后更改: 2024/01/29 11:48 由 温婕莺