题解 CF1092B 【Teams Forming】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 659 | 阅读时长 ≈ 1 分钟

这题的基本思想就是贪心吧

题目就是让你两两分组，使得每组能力值的差值最小

设$a_{1},a_{2},···,a_{n}$表示每个学生的能力值

且满足：$a_{1} \le a_{2} \le ··· \le a_{n}$

则对于任意一个能力值$a_{i}$，它的最优匹配为$a_{i+1}$（$i$为奇数）

考虑到$a_{1}$，我们不取$a_{i-1}$（你想想$a_{1-1}$是什么）

假设存在一个能力值$a_{k}$ ($k> i+1$)，使得$a_{k}-a_{i}< a_{i+1}-a_{i}$

即: $a_{k}<a_{i+1}$

∵ $a_{i+1}<a_{k}$

∴ 不存在这样的$k$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n;
int a[110],ans; 
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);//要先排序
	for(int i=1;i<=n;i+=2) //i要为奇数
	{    
		ans+=a[i+1]-a[i];//答案加上两个能力值的差
	}
	cout<<ans;
	return 0;
}