欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

优先队列解贪心封神

时间:2023-04-27

#include #include using namespace std;typedef long long LL;const int N = 2e5 + 10;LL T, n, m;struct node{LL ti, hi, z;friend bool operator < (node a, node b){return a.hi < b.hi;}}enemy[N];priority_queue > pq;int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> T;while (T--){while (!pq.empty())pq.pop();cin >> n >> m;for (int i = 1; i <= n; ++i){cin >> enemy[i].ti >> enemy[i].hi;enemy[i].hi = min(enemy[i].hi, m);enemy[i].z = enemy[i].hi - enemy[i].ti;}LL mm = m;for (int i = 1; i <= n; ++i){if (enemy[i].z >= 0)m += enemy[i].z;else pq.push(enemy[i]);}int flag = 1;while (!pq.empty()){node temp = pq.top();if (m >= temp.ti){m += temp.z;pq.pop();}else if (m < temp.ti){flag = 0;break;}}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;} return 0;}

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。