Codeforces1119B Alyona and a Narrow Fridge

原题链接:Codeforces1119B

贪心 + 二分

二分出 $k$,每次对 $1$~$k$ 排序,两个一层,倒序减一遍,剩余空间 $≥0$ ,则满足。

 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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

int n, h;
int a[N];
int b[N];

bool check(int x) {
	for (int i = 1; i <= x; i++) b[i] = a[i];
	sort(b + 1, b + x + 1);
	int space = h;
	for (int i = x; i >= 1; i -= 2) space -= b[i];
	return space >= 0;
}

int main() {   
	cin >> n >> h;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int l = 1, r = n;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;   
    return 0;
}
updatedupdated2020-05-112020-05-11
加载评论
点击刷新