洛谷

CF

分析

假設我們選出了 \(p\) 個任務，那么主席一定會將其按照： \(x.b>y.b\) ， \(x.a<y.a\) 的排序方式將其排序，然后選擇前 \(k\) 個任務完成。所以我們先按照這種方式排序，后 \(p-k\) 個是一定不會被主席選中的，可以將其打上標記。

我們的目的是讓這 \(k\) 個任務的 \(suma\) 最大，另外 \(p-k\) 個任務的 \(sumb\) 最大。然后我們將 \(n\) 個任務按照 \(x.a>y.a\) 排序，為了讓這些被主席選上，我們要以 \(x.b>y.b\) 為第二排序。這樣我們便找到了要讓主席選上的 \(k\) 個任務，即排序后的前 \(k\) 個。

最后再按照第一種排序方式排序，選擇已選中的 \(k\) 個任務后面的 \(p-k\) 個，這樣既保證了按照 \(b\) 從大到小排序，又能使 \(p-k\) 個任務的 \(maxb\) 小于 \(k\) 個任務的 \(minb\) ，即主席一定會選我們選擇好的 \(k\) 個任務。

代碼

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;template <typename T> inline void read(T &x) {T f = 1; x = 0; char c;for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);x *= f;
}struct task {int a, b, id, tag;
} t[N];int n, p, k, cnt, num;
bool vis[N];bool pre(task x, task y) {if (x.b != y.b) return x.b < y.b;if (x.a != y.a) return x.a > y.a;return x.tag < y.tag;
}bool stu(task x, task y) {return x.a == y.a ? x.b > y.b : x.a > y.a;
}int main() {read(n), read(p), read(k);for (int i = 1; i <= n; ++i) read(t[i].a), read(t[i].b), t[i].id = i;sort(t + 1, t + 1 + n, pre);for (int i = 1; i <= p - k; ++i) t[i].tag = 1;sort(t + 1, t + 1 + n, stu);for (int i = 1; cnt < k; ++i)if (!t[i].tag) {cnt++;printf("%d ", t[i].id);vis[t[i].id] = 1;t[i].tag = 2;}cnt = 0;sort(t + 1, t + 1 + n, pre);for (int i = n; cnt < p - k; --i) {if (num >= k) {cnt++;printf("%d ", t[i].id);}if (vis[t[i].id]) num++;}return 0;
}

轉載于:https://www.cnblogs.com/hlw1/p/11503125.html

總結

以上是生活随笔為你收集整理的CF332C Students' Revenge的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。