有大佬帮忙看看吗?
查看原帖
有大佬帮忙看看吗?
289573
wtxy2006楼主2020/6/20 13:57

主要思路:优先队列加贪心。

第8第10个点WA了,死活AC不了

// P6538 [COCI2013-2014#1] LOPOV
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#define MN 3000100
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return x * f;
}
struct things {
  int v, m;
  inline bool operator<(const things& t2) const { return this->v < t2.v; }
  inline bool operator==(const things& t2) const { return this->v == t2.v; }
} a[MN];
inline bool cmp(things t1, things t2) {
  return t1.m == t2.m ? t1.v > t2.v : t1.m < t2.m;
}
priority_queue<things> q;
int n, k, b[MN], ans;
int main() {
  n = read(), k = read();
  for (int i = 0; i < n; i++) a[i].m = read(), a[i].v = read();
  for (int i = 0; i < k; i++) b[i] = read();
  sort(a, a + n, cmp), sort(b, b + k);
  for (int i = 0, j = 0, g = 0; i < k; i++, g = j) {
    while (a[j].m <= b[i] && j < n) j++;
    for (int p = g; p < j; p++) q.push(a[p]);
    if (!q.empty()) ans += q.top().v, q.pop();
  }
  printf("%d", ans);
  return 0;
}
2020/6/20 13:57
加载中...