[杂题]CSUOJ1274Balls and Boxes

题目链接

题意:中文题 题意不多赘述

值得注意的是n<m 不必考虑n==m的情况 (m是盒子个数, n是每次选取的盒子个数, 不要弄反了!)

这题一看就是同余方程

每次选取n个盒子放球 也就是说每次都增加n个球

最后m个盒子中球的个数相等, 也就是最终状态球的总数为m的倍数

于是 很容易能得到同余方程:sum+x*n=y*m   (sum为出示状态共有sum个球)

其中x为 需要选x次盒子放球

  y为 最终每个盒子有y个球

接下来只要解同余方程

若无解, 则无论怎样操作都不能达到这个目的

若有解 还需满足几个条件:

  (首先需要记录一下:初始状态最多的盒子里有maxn个球, 最少的有minn个球)

  y>=maxn   也就是最后每个盒子里的球的个数 肯定要大于或者等于初始状态的 盒子中有的球的最大个数

  x>=y-minn  也就是 选盒子放球的次数 肯定要大于或者等于 最终状态每个盒子内球的个数 与 初始状态盒子中有的球的最小个数 之差

 #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cctype>
#include <cmath>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
typedef long long LL;
typedef long double LD;
const double pi=acos(-1.0);
const double eps=1e-;
#define INF 0x3f3f3f
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
typedef pair<int, int> PI;
typedef pair<int, PI > PP;
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}
//inline int read(){char ch=' ';int ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}return ans;}
inline void print(LL x){printf(LLD, x);puts("");}
//inline void read(LL &ret){char c;int sgn;LL bit=0.1;if(c=getchar(),c==EOF) return ;while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');if(c==' '||c=='\n'){ ret*=sgn; return ; }while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;ret*=sgn;} void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if(b)
{
ex_gcd(b, a%b, d, x, y);
LL tmp=x;
x=y;
y=tmp-(a/b)*y;
}
else
{
x=, y=, d=a;
return ;
}
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n, m;
scanf("%d%d", &n, &m);
int sum=, maxn=, minn=INT_MAX;
for(int i=;i<n;i++)
{
int a;
scanf("%d", &a);
sum+=a;
maxn=max(maxn, a);
minn=min(minn, a);
}
LL d, x, y;
ex_gcd(n, m, d, x, y);
if(sum%d)
printf("-1\n");
else
{
x*=sum/d;
y*=sum/d;
LL ans1=(maxn-x)*d/m;
LL ans2=(x+y-minn)*d/(n-m);
if((x+m/d*ans1)<maxn) ans1++;
if((n/d*ans2-y)<((x+m/d*ans2)-minn)) ans2++;
print(n/d*max(ans1, ans2)-y);
}
}
return ;
}

CSUOJ 1274

最后。。。以上是纯YY的结果。。。具体的证明还是直接看官方题解好了,反正我也证不出来(题解:http://acm.csu.edu.cn/csuacm/2013/04/)

上一篇:构建自己的PHP框架--实现Model类(1)


下一篇:Django实战(15):Django实现RESTful web service