[JSOI2007]建筑抢修 (贪心)

题目链接

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

[JSOI2007]建筑抢修 (贪心)

原文地址：https://www.cnblogs.com/Kv-Stalin/p/9762517.html