贪心

每次将一局的分数存入优先队列中，作为xjd的胜场分数。

进行假设，若xjd的分数大于oxx，说明有减少的余地，尝试从xjd的胜场中找出分数最小的，并减去，将其变为oxx的胜场。直到无法再减少。

代码：

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
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
ll arr[maxn];
ll n,k;
ll ans;
priority_queue<ll,vector<ll>, greater<ll> >win;
int main() {
	cin >> n >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	ans = n + 1;
	ll score_oxx, score_xjd;
	score_oxx = k;
	score_xjd = 0;
	ll cnt = 0;
	for (ll i = 1; i <= n; i++) {
		win.push(arr[i]);
		score_xjd += arr[i];
		cnt++;
		while (score_xjd>score_oxx) {
			ll tp = win.top();
			if (score_xjd - tp >= score_oxx + tp) {
				score_xjd -= tp;
				score_oxx += tp;
				win.pop();
				cnt--;
			}
			else
				break;
		}
		if(score_xjd>=score_oxx)
			ans = min(ans, cnt);
	}
	if (ans == n + 1)cout << -1;
	else cout << ans;
	return 0;
}

类似题目：

POJ 2431 Expedition

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
#include<iostream>
#include<queue>
using namespace std;
int pos, dis, ans;
int A[10010], B[10010];
int main() {
    int N, L, P;    //起初有P单位油
    cin >> N >> L >> P;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    A[N] = L;
    B[N] = 0;
    priority_queue<int>que;
    for (int i = 0; i <= N; i++) {
        dis = A[i] - pos;
        P -= dis;                //剩余油量
        while (P < 0) {
            if (que.empty()) {        //无油可加
                cout << "-1";
                cout << ans;
                return 0;
            }
            else {
                P += que.top();        //加油
                que.pop();
                ans++;
            }
        }
        pos = A[i];        //到达下一点
        que.push(B[i]);
    }
    cout << ans;
}