鎕鎕鎕 HihoCoder - 1838 (贪心+思维)

题目

https://cn.vjudge.net/problem/HihoCoder-1838

鎕鎕有 2n + 1 张卡片,每张卡片上都有两个数字,第 i 张卡片上的两个数字分别是 Ai 与 Bi。

现在鎕鎕要从所有卡片中选出恰好 n + 1 张卡片,然后计算他选出的所有卡片中 Ai 的和与 Bi 的和。他的目的是要使他选出的卡片的Ai 的和与 Bi 的和,都要分别大于剩下 n 张没选的卡片的 Ai 的和与 Bi 的和。

鎕鎕最近沉迷于玩 Switch,所以他希望你能帮他解决这个问题。

Input
输入第一行是一个整数 n,意义如以上所示。

接下来有 2n + 1 行,每行为两个正整数,第 i 行的两个正整数分别代表 Ai 和 Bi。

数据保证 1 ≤ n ≤ 100000,1 ≤ Ai, Bi ≤ 109

Output
如果无法选出 n + 1 张卡片满足鎕鎕的要求,输出一个数 -1。否则输出 n + 1 行,每行有一个正整数,表示选出的卡片编号(从 1 开始)。如果有多解,输出任意一组解均可。

Sample Input

1
2
3
4
5
6
2
4 2
9 4
5 3
7 5
8 1

Sample Output

1
2
3
3
4
2

思路

刚开始写还脑残似的写了个爆搜,我是个zz。

题目要求:选出n+1个元素使得这n+1个元素a值和b值总和分别大于其余的n个元素a值总和、b值总和。

其实对于n+1个元素或n个元素我们并不需要真的把a值总和、b值总和求出来,我们可以把问题转化成为只要对于n个元素中每个元素来说,我们都能在n+1个元素中找到一个不同的的元素,使得该元素的b的值大于那n个元素中的某元素的b的值就可以满足b的总和这一条件了。a的总和同理。

那么实际上,就可以以a值为排序的关键值对整个数组排序,接着对每两个相邻的元素,取那个b值较大的元素就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

const int MAXN=5e5+10;

struct node {
int a,b;
int index;
};
int n;
node arr[MAXN];

bool cmp(node x,node y)
{
return x.a<y.a;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=2*n+1;i++) {
scanf("%d%d",&arr[i].a,&arr[i].b);
arr[i].index=i;
}
sort(arr+1,arr+2*n+2,cmp);
int st[MAXN];
int cnt=0;
for(int i=1;i<=n;i++)
if(arr[2*i].b<arr[2*i-1].b)
st[cnt++]=(arr[2*i-1].index);
else st[cnt++]=(arr[2*i].index);
st[cnt++]=(arr[2*n+1].index);
for(int i=0;i<cnt;i++)
printf("%d\n",st[i]);
return 0;
}
-------------本文结束感谢您的阅读-------------
0%