题解 – 任务型贪心问题

最近在刷贪心水题，于是就看到有一些题都是基于一个数轴上完成最大贡献的任务的问题展开的，于是，就有了这篇题解，倒不如说是一个分类。

T1.[ABC137D] Summer Vacation

题目链接

这种题目的最常见的限制条件是每天只能做一个任务，这样我们可以采取枚举天数来解。

再来看看还有什么条件，做完工作之后要一定的天数才能拿到工资，也就是说那些超出天数限制的任务都做不了，我们可以在读入的时候就排除这些选项。

既然要最大化收益，我们就可以按照收益排序，但是有限制条件。

首先可以想到将所有工作按照收益从大到小排序，然后倒序枚举天数，把最大的收益的工作最靠右的工作的时间标记vis，不过这样复杂度可能会被卡成\mathcal{O}(n^2)的。

考虑优化，我们可以使用一个优先队列，还是从右枚举，往左枚举天数的时候，就可以把这天刚好可以有收入的那些工作加入到优先队列，这样每个没有访问的天都是取到当前可以取的最大的收益，而复杂度也降到\mathcal{O}(nlog_n)。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e5 + 10;
inline int read() {
  char ch = getchar(); int p = 1, x = 0;
  while(!isdigit(ch)) {if(ch == ' ') {p = -1;} ch = getchar();}
  while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
  return x;
}
priority_queue<int> q;
int n, m;
int u, v;
vector<int> rec[N];
signed main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    cin >> u >> v; 
    if(m - u + 1 >= 1) rec[m - u + 1].push_back(v);
  }
  ll ret = 0;
  for(int i = m; i >= 1; i--) {
    for(auto j : rec[i]) {
      q.push(j);
    }
    if(!q.empty()){ret += q.top(); q.pop();}
  }
  cout << ret << endl;
  return 0;
}

T2.[USACO09OPEN] Work Scheduling G

[题目链接]

题目大意其实跟上一题差不多。虽然数据比较大，但是不需要离散化，直接按照任务的个数从右到前枚举。如果当前没有任务了，直接把时间点跳到下一个任务。依旧用优先队列维护。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);

inline int read() {
  char ch = getchar(); int p = 1, x = 0;
  while(!isdigit(ch)) {if(ch == ' ') {p = -1;} ch = getchar();}
  while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
  return x * p;
}
const int N = 1e5 + 10;
int n;
priority_queue<ll> q;
ll ret;
struct num{ll d, p;}a[N];
inline bool cmp(num x, num y) {
  return x.p > y.p;
}
int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  cin >> n;

  for(int i = 1; i <= n; i++) {
    cin >> a[i].p >> a[i].d;
  }

  stable_sort(a + 1, a + n + 1, cmp);
  int i = 1;
  int pos = a[i].p;
  while(i <= n) {
    int pt = a[i].p, pos = pos == a[i].p ? pos : a[i].p;
    while(a[i].p == pt) {
      q.emplace(a[i].d);
      i++;
    }
    while(pos > a[i].p and !q.empty() and pos >= 1) {
      ret += q.top(); q.pop();
      pos--;
    }
    // i++;
  }
  cout << ret;
  return 0;
}