【每日一题】tokitsukaze and Soldier 题解

Solution

看了一圈题解都是优先队列, 这里给个不正经的做法
观察到人数只会在 到
我们考虑会不会出现一个峰值使得结果最大

即这个结果是不是满足凹凸函数的定义
我们考虑三分人数大小, 这样可以取得一个局部极值
然后在这个局部极值的附近找是否有最优的
问题在于三分出人数后如何去check贡献
因为我们已经知道了人数
于是那些 比当前人数小的都不能选
剩下的那些只需要按 排序一个一个选即可
虽然我觉得我的做法很假
但是就是过了啊hhhh

update

被 了
老老实实写优先队列吧
首先按 排序, 然后以 值建立一个小根堆(优先队列)
然后对于当前的 先进入队列(注意这一步很重要, 判断完再进队是错的)
为什么是错的? 因为这个点我们可能根本就不需要取, 所以不能弹出多余的元素再入队, 要直接入队
然后此时判断 跟队列大小, 弹出队里最小的元素
在模拟的过程中不断更新答案即可

正解Code

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const ll mod = 23333333333333333;
struct node {
  ll v, s;
  bool operator < (const node &s) const {
    return v < s.v;
  }
}a[N];
int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i].v >> a[i].s;
  }
  sort(a + 1, a + 1 + n, [](const node &x, const node &y) {return x.s > y.s;});
  priority_queue<ll, vector<ll>, greater<ll> > q;
  ll ans = 0, res = 0;
  for(int i = 1; i <= n; i++) {
    q.push(a[i].v);
    res += a[i].v;
    while(!q.empty() && q.size() > a[i].s) res -= q.top(), q.pop();
    ans = max(ans, res);
  }
  cout << ans << '\n';
  return 0;
}

三分水过Code

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const ll mod = 23333333333333333;
struct node {
  ll l, r;
  bool operator < (const node &s) const {
    return l > s.l;
  }
}a[N];
int n;
ll val(int x) {
  int last = x;
  ll res = 0;
  for(int i = 1; i <= n; i++) {
    if(x <= a[i].r) {
      res += a[i].l;
      last--;
    }
    if(!last) break;
  }
  return res;
}
int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
  sort(a + 1, a + 1 + n);
  int left = 1, right = n; // 三分人数
  while(right - left > 5) {
    int mid = left + right >> 1;
    int midmid = mid + right >> 1;
    if(val(mid) >= val(midmid)) {
      right = midmid - 1;
    }
    else left = mid + 1;
  }
  ll ans = 0;
  for(int i = max(1, left - 100); i <= min(n, left + 100); i++) ans = max(ans, val(i));
  cout << ans << "\n";
  return 0;
}