558 字
3 分钟
COGS 2235 烤鸡翅
【题目描述】
在焦作太行路上,有一家烤鸡翅的生意火爆。因为好吃,所以卖的特别好。排队的人就特别多,经常有很多人买不到鸡翅。 鸡翅会在每分钟烤出Xi个,每分钟也只会卖给一个客人,第i个客人需要买Yi个。因为生意火爆,老板可以选择在这分钟不卖给这个客人鸡翅,或者卖给这个顾客他需要的鸡翅, 如果现在剩余的鸡翅不够,那就肯定不能卖给这个客人。无论这个客人能否买到鸡翅,他必须离开队伍。 现在给定N分钟,且已经知道每分钟烤出的鸡翅个数Xi,也知道每个客人需要鸡翅的Yi个数,现在老板想知道,如何合理安排卖给与拒绝,最多可以满足多少人
【输入格式】
第一行一个正整数N,表示有N分钟的时间卖鸡翅 第二行N个用空格隔开的整数 X1,X2……Xn,Xi表示第i分钟会有Xi个鸡翅烤出 第三行N个用空格隔开的整数Y1,Y2……Yn,Yi表示第i分钟的顾客需要Yi个鸡翅
【输出格式】
一个整数,表示最多可以满足买到鸡翅的人数。
【样例输入】
6
2 2 1 2 1 0
1 2 2 3 4 4
【样例输出】
3
【数据范围】
50% 数据保证 N<=1000 100% 1<=N<=250000 Xi,Yi都在[0,10^9]范围内
题解
能卖就卖
卖不了了如何以前有人买的数目比他多
那就不卖给以前的那个人了也就是收回来
可后悔的贪心,长见识了。
主要使用优先队列
#include <cstdio>#include <cstring>#include <queue>using namespace std;int x[250005], y[250005];class comp{ public: bool operator()(long long a, long long b) { return y[a] < y[b]; }};priority_queue<long long, vector<long long>, comp> Q;int main(){ freopen("wing.in", "r", stdin); freopen("wing.out", "w", stdout); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &x[i]); for (int i = 1; i <= n; i++) scanf("%d", &y[i]); long long sum = 0; for (int i = 1; i <= n; i++) { sum += x[i]; if (sum >= y[i]) sum -= y[i], Q.push(i); else { if (!Q.empty()) { if (y[Q.top()] > y[i]) { sum += y[Q.top()]; Q.pop(); sum -= y[i]; Q.push(i); } } } } printf("%d\n", Q.size());}