Codeforces-Global-Round-25

C. Ticket Hoarding

题意

给定一个长度为 的正整数数组 ，求一个正整数数组 在满足=k的条件下，求的最小值。

解题思路

将上述式子进行变形：

故要使上式值最小，则应使尽可能的大，而要使尽可能的大，

等价于：较小的尽可能匹配较大的，较大的尽可能匹配较小的

由此可通过将进行排序(从小到大)，将的前项置，第项置,后面全置，可得到最优解

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
  int n,m,k;
  cin>>n>>m>>k;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a.begin(),a.end());
  ll ans=1ll*k*k;
  for(int i=0;i<n;i++){
    if(k>=m){
      ans-=1ll*(m-a[i])*(m-a[i]);
      k-=m;
    }else if(k>0){
      ans-=1ll*(k-a[i])*(k-a[i]);
      k=0;
    }else ans-=1ll*a[i]*a[i];
    ans+=1ll*a[i]*a[i];
  }
  cout<<ans/2<<"\n";
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}