AHSOFNU NOIP模拟题-15 T1(二分)

最大的最小,显然二分,而且这题是裸二分,二分以后贪心判断就行

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "money"
using namespace std;
const int MAXN = 100000 + 5;
int n, m, vi[MAXN];
LL totv;
bool check(LL x) {
LL ret = 1, tot = 0;
for (int i=1;i<=n;i++) {
if ((LL)vi[i] > x) return false;
if (tot + (LL)vi[i] <= x) {
tot += (LL)vi[i];
} else ret++, tot = (LL)vi[i];
}
return m >= ret;
}
void clean() {
totv = 0;
}
void solve() {
clean();
for (int i=1;i<=n;i++) scanf("%d", &vi[i]), totv += (LL)vi[i];
LL ans = 0, l = 0, r = totv + 1;
while (l < r) {
LL mid = (l + r) / 2;
if (check(mid)) {
ans = r = mid;
} else l = mid + 1;
}
printf("%I64d\n", ans);
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
scanf("%d%d", &n, &m), solve();
fclose(stdin); fclose(stdout);
return 0;
}

工资
(money/money.in/money.out)
时限1000ms 内存256MB
聪哥在暑假参加了打零工的活动,这个活动分为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

------ 本文结束 ------