这是我第一次做到反悔贪心的题目
第
座建筑有两个参数:需要
秒维修以及需要在
秒之前完成维修,否则报废
无论是按照
从小到大排序或者
从小到大排序都会有个问题,就是可以一开始就选择了很不好的选择,例如我按照
从小到大排序,我的想法是物品维修时间小的先修,维修时间大的后修。
反例:
10 30
20 20
如果我先维修第一个,那么就不能维修第二个了;但是如果我先维修第二个,那么也可以继续维修第一个。
如何确定那个先修,那个后修呢?这与它们的紧张度。
在这道题目里面,由
决定,所以我们需要按照
从小到大排序。但是也会出现上面反例的情况,这时候就需要做出反悔了,我将之前一个耗时大的给删除掉,意思就是之前维修时间很大的一个建筑我反悔了,我不修了。那么我现在消耗的总时间就减少了
,那么就更优的继续选择.
证明为什么是按照
从小到大排序:
假设我先维修第
座建筑可以,然后再维修第
座建筑也可以:那么
,
假设我先维修第
座建筑可以,然后再维修第
座建筑也可以:那么
,
所以有:
,所以
所以按照
从小到大排序
定义
表示我在维修过程中消耗的总时间,
表示第
座建筑需要维修的时间,
表示第
座建筑需要在此之前完成维修。
-
如果
,那么我直接就维修这个物品,所以
,
-
如果
,那么如果之前存在一个建筑的维修时间比现在
大,那么我是不是就可以将之前的这个建筑给删除掉,进而维修现在的
,那么
不变,因为之前的维修时间大于
,那么既然将之前的一个建筑删了,那么现在的
一定是可以维修的;并且总时间
但是如何找到之前已经维修的所有建筑里面维修时间最大的一个建筑呢?对,聪明的你已经想到了用
来维护最大值!
完整的思路:
-
如果
,那么我直接就维修这个物品,所以
,
-
如果
,那么如果
,那么
,
,
因为优先队列里面的元素表示的就所有已经维修的建筑的维修时间,所以最终
就是答案,
就多余了
总代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
bool cmp(pair<int, int> a, pair<int, int> b){
return a.second < b.second;
}
signed main(){
HelloWorld;
int n; cin >> n;
vector<pair<int, int> > a(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
sort(a.begin() + 1, a.begin() + 1 + n, cmp);
priority_queue<int> q;
int time = 0;
for(int i = 1; i <= n; i ++){
if(time + a[i].first <= a[i].second){
time += a[i].first;
q.push(a[i].first);
}
else if(q.size() && q.top() > a[i].first){
time += a[i].first - q.top();
q.pop();
q.push(a[i].first);
}
}
cout << q.size() << endl;
return 0;
}`



京公网安备 11010502036488号