我是靠谱客的博主 碧蓝石头,这篇文章主要介绍Codeforces 551C GukiZ hates Boxes 二分答案,现在分享给大家,希望可以做个参考。

题目链接

题意:

 一共有n个空地(是一个数轴,从x=1 到 x=n),每个空地上有a[i]块石头
 有m个学生
 目标是删除所有石头
 一开始所有学生都站在 x=0的地方
 每秒钟每个学生都可以在原地删除一块石头,或者向 → 移动一格距离
 问:删除所有石头的最短时间

案例解析:
 3 2 
1 0 2

 第一个学生第一秒向→走,第二秒删a[1]的一块石头
 第二个学生一直走到头,删掉a[3] ,所以第二个学生花费是 1+1+1+2 = 5
两个学生可以同时运动。

思路:

二分答案,设答案为x,即需要x秒来搬完石头

 先拿一个学生来
 总要有一个学生来搬最远的那堆石头的
先让这个学生走到尽头

 这个学生拥有的时间就是x
 那么走到尽头后,还剩下的时间用来搬最后一堆石头
 如果这堆石头搬不完,那么这个学生就利用完了,换一个学生
 如果搬的完  那么这个学生还剩下的时间可以用来搬前一堆石头 一直把这个学生利用完。
 
如果所有学生都利用完了石头还是搬不完,那么x秒肯定是不够的
 否则x秒就是够的

复制代码
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
65
66
67
68
69
70
71
72
73
74
75
#include <iostream> #include <string> #include <vector> #include <cstring> #include <cstdio> #include <map> #include <queue> #include <algorithm> #include <stack> #include <cstring> #include <cmath> #include <set> #include <vector> using namespace std; template <class T> inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template <class T> inline void pt(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) pt(x / 10); putchar(x % 10 + '0'); } typedef long long ll; typedef pair<ll, ll> pii; const int inf = 1e9; const int N = 1e5 + 10; int n, m; int a[N], b[N]; bool ok(ll x) { for (int i = 1; i <= n; i++)b[i] = a[i]; int top = n, tmp = m; while (tmp-->0 && top) { ll lef = x - top; while (lef && top) { if (b[top] == 0) { top--;continue; } if (b[top] <= lef) { lef -= b[top--]; } else { b[top] -= (int)lef;lef = 0; } } } while (top && b[top] == 0)top--;//找到最后一个并且不是0的点 return top == 0; } int main() { rd(n); rd(m); int d = 1; for (int i = 1; i <= n; i++) { rd(a[i]); } while (a[n] == 0)n--; //把最后的0删掉 ll l = 1, r = 1e15, ans; while (l <= r) { ll mid = (l + r) >> 1; if (ok(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } pt(ans); return 0; }



最后

以上就是碧蓝石头最近收集整理的关于Codeforces 551C GukiZ hates Boxes 二分答案的全部内容,更多相关Codeforces内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(84)

评论列表共有 0 条评论

立即
投稿
返回
顶部