題目鏈接

Solution

可以考慮 \(dp\) ,但是很顯然 \((n^2)\) 降不下來.
然后考慮貪心,首先,絕對的正確的是,在同等的情況下,給后面的留更多的時間.
首先按照 \(T_2\) 排序.
然后我們維護一個大根堆 每修理一棟建筑 我們就把這棟建筑的T1值加入堆 若當前無法修理 我們判斷堆頂是否比這棟建筑的T1大 如果大 取消修理堆頂，改為修理當前建筑.

Code

#include<bits/stdc++.h> using namespace std; const int N = 2e5+10,inf = 2e9, mod = 1e9+7; typedef long long ll; int n; pair<int ,int > P[N]; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&P[i].second,&P[i].first);int ans = 0;ll tmp = 0;sort(P+1,P+n+1);priority_queue<int > q;for(int i=1;i<=n;i++){if(P[i].first>=P[i].second+tmp) q.push(P[i].second),ans++,tmp+=P[i].second;else{if(q.empty()) continue;int k = q.top();if(k>P[i].second){tmp-=k;tmp+=P[i].second;q.pop();q.push(P[i].second);}}}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/Kv-Stalin/p/9762517.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[JSOI2007]建筑抢修 (贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。