首页 > 代码库 > Codeforces 798D Mike and distribution（贪心或随机化）

Codeforces 798D Mike and distribution（贪心或随机化）

2024-11-02 11:40:39   206人阅读

题目链接 Mike and distribution

题目意思很简单，给出$a_{i}$和$b_{i}$，我们需要在这$n$个数中挑选最多$n/2+1$个，使得挑选出来的

$p_{1}$,$p_{2}$,$p_{3}$,...,$p_{m}$满足

$a_{p1}+a_{p2}+a_{p3}+...+a_{p_{m}}>a_{1}+a_{2}+a_{3}+...+a_{n}$

$b_{p1}+b_{p2}+b_{p3}+...+b_{p_{m}}>b_{1}+b_{2}+b_{3}+...+b_{n}$

$m <= n/2+1$

打这场比赛的时候怎么也想不到……眼睁睁看着自己掉分

后来看了别人的代码才恍然大悟。

 

贪心做法：

因为$a_{i}$和$b_{i}$都是正数，那么就直接令$m = n/2+1$

先对$a$降序排序，然后排完序之后的$1$号必选

然后在剩下$n-1$个数中，每相邻两个数分成一组，在每一组中选$b_{i}$较大的那个，就可以了。

 

#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)	for (int i(a); i <= (b); ++i)#define dec(i, a, b)	for (int i(a); i >= (b); --i)struct node{	int x, y, id;} a[100010];int n;set <int> s;int main(){	scanf("%d", &n);	rep(i, 1, n) scanf("%d", &a[i].x);	rep(i, 1, n) scanf("%d", &a[i].y);	rep(i, 1, n) a[i].id = i;		sort(a + 1, a + n + 1, [](node a, node b){return a.x > b.x;});	s.insert(a[1].id);	for (int i = 2; i <= n; i += 2){		int j = i + 1;		if (j <= n && a[j].y > a[i].y) s.insert(a[j].id); else s.insert(a[i].id);	}	printf("%d\n", n / 2 + 1);	for (auto u : s) printf("%d\n", u);	return 0;}

 

不过这道题还有另一种解法……那就是……随机化……

 

#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)	for (int i(a); i <= (b); ++i)#define dec(i, a, b)	for (int i(a); i >= (b); --i)#define LL		long longconst int N = 100010;LL a[N], b[N], A = 0, B = 0;int p[N], n, k;int main(){	scanf("%d", &n);	rep(i, 1, n) scanf("%d", a + i), A += a[i];	rep(i, 1, n) scanf("%d", b + i), B += b[i];	rep(i, 1, n) p[i] = i;	srand(time(0)); 	k = n / 2 + 1;	while (true){		LL x = 0, y = 0;		random_shuffle(p + 1, p + n + 1);		rep(i, 1, k) x += a[p[i]], y += b[p[i]];		if (2 * x > A && 2 * y > B){			printf("%d\n", k);			rep(i, 1, k) printf("%d\n", p[i]);			return 0;		}	}	return 0;}

 真的让我惊呆了……

Codeforces 798D Mike and distribution（贪心或随机化）


联系
我们