每日一题 [JSOI2007]建筑抢修

这题的思路和https://ac.nowcoder.com/acm/problem/50439 类似
在我们看来，每一段都存在一个截至区域，首先肯定是要把截至区域按从小到大的顺序排列，这样之前的选择会为后面的选择腾出更多的时间，这个贪心就是可行的。
既然所选需要最多，有些我选择过后，如果当前总和小于截至日期，直接选择，但是后期选择的时候你会发现个问题，如果你选择当前的，结果后期的修理时间比他小的值可能无法在截至日期前完成，那么就会缩小选择区域，那么我们可以用后者替换当前已选择的最大修理时间那个，因为截止时间从小到大排列，把修理时间多的改为少的，可行性会更优。
所以我们只需要弄个优先队列，每次找出已选择的最大修理时间，如果当前修理时间小于它，则可以替换

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn=2e5+7;
priority_queue<int> pa;

struct node {
  int v,s;
}a[maxn];

bool cmp(node a,node b)
{
  return a.s<b.s;
}

signed main()
{

  int n;
  cin>>n;
  for (int i=1;i<=n;++i)
  {
    cin>>a[i].v>>a[i].s;
  }
  sort(a+1,a+n+1,cmp);///反排序
  int cnt=1,ans=a[1].v;
  pa.push(a[1].v);
  for (int i=2;i<=n;++i)
  {
    if ((ans+a[i].v)<=a[i].s)///当前可选直接选
    {
      pa.push(a[i].v);
      ++cnt;
      ans+=a[i].v;
    }
     else if (a[i].v<pa.top())///如果不可选，则看是否可以使得解更优
      {
        ans-=pa.top();
        pa.pop();
        pa.push(a[i].v);
        ans+=a[i].v;
      }
  }
  cout<<cnt<<endl;
  return 0;
}