贪心思路:每次修缮剩余时间最小的且可以修缮的建筑。
没有严谨的正确性证明所以挂掉了,但我还是想知道它在什么样的数据下会出错。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1.5e5+10;
#define int long long
priority_queue< pair<int,int> > heap;
int sub;
int tim[maxn];
signed main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tim[i];
int tmp;cin>>tmp;
heap.push(make_pair(-tmp,i));
}
int ans=0;
for(int i=1;i<=n;i++)
{
pair<int,int> tmp;
tmp=heap.top();
heap.pop();
if((-tmp.first)-sub>=tim[tmp.second])
{
sub+=(tim[tmp.second]);
ans++;
}
}
cout<<ans;
return 0;
}