题解 AT2361 [AGC012A] AtCoder Group Contest

2024-10-20 17:29:08

\(\sf{Solution}\)

显然要用到贪心的思想.

既然最终的结果只与每组强度第二大选手有关，那就考虑如何让他的值尽可能大.

其实，从小到大排个序就能解决，越靠后的值越大，使得每组强度第二大选手的值最大.

最后 \(O(n)\) 扫一遍，更新 \(ans\) 的值.

\(\sf{Code}\)

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

ll n,a[300005],ans;

inline bool cmp(int x,int y){return x<y;}

signed main()

{

	ios::sync_with_stdio(false);

	cin>>n;

	int mn=n*3;

	for(int i=1;i<=mn;++i)

		cin>>a[i];

	sort(a+1,a+mn+1,cmp);//排序

	for(int i=mn-1;i>=n+1;i-=2)

		ans+=a[i];//逐一统计每组的值，更新ans

	cout<<ans<<"\n";//atcoder 换行

	return 0;

}

最新文章

热门文章