比赛 |
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;
}