A. Load Balancing
很明显题意要的就是让我们把每个数往平均值靠，这样就保证最大值-最小值最小
但是当sum%n ！=0的时候就说明无法每个数都等于sum/n，所以处理的方法就是，先计算这些无法等于sum/n的个数cnt，再算出可以到达sum/n的次数n-cnt，然后算出总代价，再用总代价除以2就是答案，因为一个数的增值是由另一个数的减值来的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,sum=0,minn=1e10,maxx=-1;
cin>>n;
vector<int>ve(n);
for(int i=0;i<n;i++){
cin>>ve[i];
sum+=ve[i];
maxx=max(maxx,ve[i]);
minn=min(minn,ve[i]);
}
if(maxx-minn<=1) {
cout<<0<<endl;
return;
}
sort(ve.rbegin(),ve.rend());//按降序排序
int cnt=sum%n,k=sum/n;
//k为向下取整后的均值
//大的向k+1靠，小的向k靠，这样保证总代价最小
int ans=0;
for(int i=0;i<n;i++)
{
if(cnt)
{
cnt--;
ans+=abs(ve[i]-k-1);
}else{
ans+=abs(ve[i]-k);
}
}
cout<<ans/2;
}
signed main()
{
int t=1;
//cin>>t;
while(t--) solve();
}
B. Longest Simple Cycle
一道比较好理解的dp
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n;
cin>>n;
int f[n+1]={0};
vector<int>a(n+1),b(n+1),c(n+1);
//c存链的顶点数，b，c为连接位置
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=2;i<=n;i++)
{
if(a[i]==b[i]) f[i]=c[i]+1;
else{
f[i]=max(c[i]+1+f[i-1]-abs(a[i]-b[i]),c[i]+1+abs(a[i]-b[i]));
}
}
cout<<*max_element(f+1,f+n+1)<<endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
C. Match Points
二分答案，枚举可以匹配的点对数，但是check里的验证，是这样的，比如 5 7 8 9 10，我枚举的mid=2，那么我要验证的是（5，9）和（7，10）这样才能确保得到的点对数最大
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>ve;
int n,z;
bool check(int mid)
{
for(int i=1;i<=mid;i++) if(ve[n-mid+i]-ve[i]<z) return 0;
return 1;
}
void solve()
{
cin>>n>>z;
ve.resize(n+1);
for(int i=1;i<=n;i++) cin>>ve[i];
sort(ve.begin()+1,ve.end());
int l=0,r=n>>1,mid=0;//边界r不可以开太大了
int ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans;
}
signed main()
{
int t=1;
//cin>>t;
while(t--) solve();
}
D. Vus the Cossack and a Contest
水题
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,m,k;
cin>>n>>m>>k;
if(n<=min(m,k)){
cout<<"Yes";
}
else cout<<"No";
}
signed main()
{
int t=1;
//cin>>t;
while(t--) solve();
}