题解 | 小红拿石子1.0

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//简单思考一下 小红的最优操作肯定是每次拿最大的一堆石子
//小紫的最优操作就是单纯的每堆拿一个
//简单模拟一下 小红拿的第一堆石子 小紫拿了0个
//小红拿的第二堆石子 小紫拿了里面的1个
//所以小红拿的第n堆石子 小紫拿了n-1个
//所以我们将数组排序 从大到小让sum+（a[i]-i）即可
//当a[i]-i==0时停止 此时全部石子被拿完
	ll n,sum=0;
    cin >> n;
    vector<ll>a(n,0);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end(),greater<int>());
    for(int i=0;i<n;i++)
    {
        if(a[i]-i<=0) break;
        sum+=(a[i]-i);
    }
    cout << sum;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;

	while(t--)
	{
		solve();
	}
	return 0;
}