Codeforces596C Wilbur and Points(贪心)

@(K ACMer)

题意:
给你一个点集,每个点的weight为$(y - x)$,你需要给出这些点的一个排列,这些点满足:如果$y2 >= y1 且x2 >= x1$$,就必须让$(x2,y2)$排在$(x1,y1)$后面.显然满足这个点集可能有多个排列满足这个条件. 然后给你一个weight的排列:$w_1,w_2,w_3....w_n$,问你是否有满足以上条件的排列同时它的weight为上序列?
分析:
这里的核心思想就是贪心:对于同一个weight的这些点,我们在越往前取用其中一个的时候,需要取用最小的,那么如何定义这个最小呢?
我们知道,如果x和y同时比一个数大于等于那么他就更大,如果只有x等于y小于呢?我们就把y大的尽量靠前,反正这样又不吃亏.
而且恰恰pair 的自带比较函数,就完美的契合了这个贪心思想.所以我用了一个set >来实现.

code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
#define xx first
#define yy second
const int mod = int(1e9) + 7, INF = 0x3fffffff, maxn = 1e5 + 40;
int n, m, a[maxn];
pii v[maxn], ans[maxn];
set st[maxn * 2];
set::iterator it;int main(void) {scanf("%d", &n) ;for (int i = 0; i < n; i++)scanf("%d%d", &v[i].xx, &v[i].yy), st[v[i].yy - v[i].xx + maxn].insert(v[i]);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);a[i] += maxn;}bool ok = true;pii maxs(-INF, -INF);for (int i = 0; i < n; i++) {if (st[a[i]].empty()) {ok = false;break;}it = st[a[i]].begin();ans[i] = *it;st[a[i]].erase(it);if (ans[i].xx <= maxs.xx && ans[i].yy <= maxs.yy) {ok = false;break;}maxs = max(maxs, ans[i]);}if (ok) {puts("YES");for (int i = 0; i < n; i++) {printf("%d %d\n", ans[i].xx, ans[i].yy);}} else puts("NO");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！