【UOJ649】游泳

大佬教程收集整理的这篇文章主要介绍了【UOJ649】游泳，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

传送门

题意：

已知一个正整数数组 (a) 的长度是 (m) ，里面所有数字的和是 (n) 且任何两个相邻数字差的绝对值不超过 (K). 求 (a) 最大的可能方差乘上 (m^2) 的结果。如果 (a) 不存在输a出 (-1).

多测，(n,k le 10^8,m le 100)

首先特判 (n<m) 和 (k=0) 的情况，这是简单的。

考虑方差计算公式

其中 (overline{a}) 为 (a) 的平均数。其乘上 (m^2) 后化简为

(ms^2=(msum a_i^2)-n^2).

所以我们只需要最大化 (sum a_i^2) 的值即可。

考虑由基本不等式得到 ((x+y)^2>x^2+y^2). 所以差尽可能大，即 (x+1,y-1) 会比 (x,y) 优秀.

因此考虑让前面的数差为 (k)，剩下的数字从后往前添加即可。（从前往后填会有一个位置差为 (k+1)）

但注意到每段非空所以开始的时候每一段都 (+1) 然后 (n leftarrow n-m).

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define op(X) ((x&1)?x+1:x-1)
#define odd(X) (x&1)
#define even(X) (!odd(X))
#define lc(X) (x<<1)
#define rc(X) (lc(X)|1)
#define lowbit(X) (x&-X)
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
#define next Cry_For_theMoon
#define il inline
#define pb(X) push_BACk(X)
#define is(X) insert(X)
#define sit set<int>::iterator
#define mapit map<int,int>::iterator
#define pi pair<int,int>
#define ppi pair<int,pi>
#define pp pair<pi,pi>
#define fr first
#define se second
#define vit vector<int>::iterator
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
using namespace std;
const int MAXN=110;
ll T,n,m,k,c[MAXN],ans;
int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&n,&m,&k);
		if(n<m){printf("-1n");conTinue;}
		if(!k){printf("%dn",(n%m)?-1:0);conTinue;}
		ans=-n*n;
		rep(i,1,m)c[i]=1;
		n-=m;
		rep(i,1,m){
			//前i个+=k
			ll use=i*k;
			if(use>n || i==m){
				ll rest=n; 
				rep(j,1,i)c[j]+=rest/i;
				rest%=i;
				rep(j,1,rest){
					c[i-j+1]++;
				} 
				break;
			}else{
				rep(j,1,i)c[j]+=k;
				n-=use;
			}
		}
		rep(i,1,m)ans+=m*c[i]*c[i];
		cout<<ans<<endl;
	}

	return 0;
}

大佬总结

以上是大佬教程为你收集整理的【UOJ649】游泳全部内容，希望文章能够帮你解决【UOJ649】游泳所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。