题解 CF1092B 【Teams Forming】

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

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

\(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

#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;
}
相关文章
相关标签/搜索