求hack一个贪心
查看原帖
求hack一个贪心
264548
Tangent233楼主2023/5/22 21:40

贪心思路:每次修缮剩余时间最小的且可以修缮的建筑。 没有严谨的正确性证明所以挂掉了,但我还是想知道它在什么样的数据下会出错。

#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;
}
2023/5/22 21:40
加载中...