比赛 20160415 评测结果 C
题目名称 烤鸡翅 最终得分 0
用户昵称 Fmuckss 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2016-04-15 15:56:24
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
int n; 
int a[250050], b[250050];


class voilence {
private:
	LL f[1005][1005];
public:
	void solve() {
		memset(f, -127, sizeof(f));
		f[0][0] = 0;
		for(int i = 1; i <= n; i++) {
			for(int k = 0; k < i; k++) {
				if(f[i-1][k] >= 0 && f[i-1][k] + a[i] - b[i] >= 0) {
					f[i][k+1] = max(f[i][k+1], f[i-1][k] + a[i] - b[i]);
				}
				if(f[i-1][k] >= 0) f[i][k] = max(f[i][k], f[i-1][k] + a[i]);
			}
		}
		/*
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j <= i; j++) {
				printf("f[%d][%d] = %d\n", i, j, f[i][j]);
			}
		}
		*/
		for(int i = n; i >= 0; i--) {
			if(f[n][i] >= 0) {
				printf("%d\n", i);
				return;
			}
		}
	}
}vl;

class greedy {
public:
	void solve() {
		priority_queue<int> q;
		LL le = 0;
		int ans = 0;
		for(int i = 1; i <= n ; i++) {
			le += a[i];
			if(le < b[i]) {//剩余的不够了 
				if(!q.empty() && q.top() > b[i]) {
					le += q.top() - b[i];
					q.pop();
					q.push(b[i]);
				}
				//当前最坏的情况就是不加,这一位要么加进去,要么不加,如果加进去反而更优那就直接加 
			} else {
				le -= b[i];
				q.push(b[i]);
				ans++;
			}
		}
		printf("%d\n", ans);
	}
}gd;

void read() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
	}
}

void solve() {
	if(n <= 1e3) {
		vl.solve();
	} else {
		gd.solve();
	}
} 

int main() {
	freopen("wing.in", "r", stdin);
	freopen("wing.out", "w", stdout);
	read();
	solve();
	return 0;
}