題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)土球，初始時(shí)的穩(wěn)定性為m，現(xiàn)在需要撞擊n個(gè)障礙，每撞擊掉第i個(gè)障礙物后，會(huì)降低a[i]的穩(wěn)定性，但會(huì)增加b[i]的穩(wěn)定性，若土球的穩(wěn)定性小于0，則會(huì)直接散架，問能否在讓土球按照一定次序撞擊掉所有木塊后仍然不散架

題目分析：直接貪心即可，我們?cè)O(shè)c為b-a，也就是撞擊第i個(gè)障礙物后對(duì)土球的貢獻(xiàn)值，顯然當(dāng)c大于0的時(shí)候，我們需要優(yōu)先撞擊這些障礙物，撞擊的次序肯定是優(yōu)先撞擊a較小的，但當(dāng)c為非正數(shù)我們?cè)撛趺崔k呢，一開始我想的是按照a的降序排序，因?yàn)閏對(duì)土球的貢獻(xiàn)為負(fù)，所以每次土球的穩(wěn)定性肯定越來越小，所以趁著穩(wěn)定性比較大的時(shí)候，將可以撞掉的障礙物都撞掉即可，但這個(gè)貪心策略并不是最優(yōu)的，隨便出一組數(shù)據(jù)就可以hack掉：

2 11

10 1

9 8

顯然答案應(yīng)該是YES，我們先選擇第二個(gè)障礙，然后再選擇第一個(gè)障礙，但如果按照a降序來選擇的話，那么返回的答案應(yīng)該是NO，又仔細(xì)思考了一下，就感覺要應(yīng)該按照b的降序排序了，因?yàn)閏一定是非正數(shù)，所以a一定大于等于b，如果按照b降序排序的話，這也就大體限制了a的范圍，但如果按照a降序排序的話，就無法限制b的范圍了（只知道b小于a），其實(shí)也可以換個(gè)角度，假設(shè)按照上述規(guī)則排好序的障礙物都可以依次擊破，那么每次擊破后的穩(wěn)定性至少為b，因?yàn)閎是可以對(duì)穩(wěn)定性貢獻(xiàn)一個(gè)正數(shù)的存在，按照b遞減排序的話，也正是和穩(wěn)定性m遞減的趨勢(shì)相同，但如果采取對(duì)于a遞減排序的話，就無法得到這個(gè)結(jié)論了

大概就是這樣一個(gè)貪心策略吧，我也證不太明白，不過自己寫幾組數(shù)據(jù)總是可以看出來的嘛

一個(gè)小破題卡了我一個(gè)小時(shí)。。以為m沒開longlong，忘記計(jì)算最大上限了，若給出的數(shù)據(jù)的n為5e5，每次的a都是0，b都是1e5，那么答案肯定就爆掉int了，所以一直只通過了80%的樣例，自閉了一個(gè)小時(shí)，還害的zx學(xué)長(zhǎng)也陪著我一直debug

這個(gè)題目真的無力吐槽了，考貪心就考貪心唄，為什么出這種惡心人的數(shù)據(jù)卡人，難頂

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;LL n,m;struct Node {int a,b,c;void cal(){c=b-a;}bool operator<(const Node& t)const{if(c*t.c<0)return c>t.c;else if(c>0)return a<t.a;elsereturn b>t.b;} }a[N];bool check() {for(int i=1;i<=n;i++){m-=a[i].a;if(m<0)return false;m+=a[i].b;}return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].a,&a[i].b);a[i].cal();}sort(a+1,a+1+n);if(check())printf("Yes\n");elseprintf("No\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 「土」巨石滚滚(贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。