题目链接：http://soj.me/show_problem.php?pid=1047

题目的大致意思：

给定两个数A，B

给定一个范围left，right，把区间[left,right]中的所有数自主分配给A和B两个数，让其分别与A和B相加之后的结果相等，如果可以，则输出possible；否则，就输出not possible

算法思想：

假设A为56，B为34，区间为[20,24]

1.先判断A和B的差是否和区间所有数的和相同，即56-34 是否等于20+21+22+23+24；（等于一次提前剪枝）

2.设区间数的个数为N，将N分为两堆（每堆至少一个，没有的情况在1中已经计算），i个和N-i个，针对每一个i的情况，计算两个堆之间差的取值范围，即max和min。

max：2*(i*right-i*(i-1)/2)-sum //sum为区间所有值的和

这种计算方法是，假设i堆的所有值为24，区间最右的i个数，是形成差值最大的方式，假如i=3，则取24,23,22。再计算每个值同24的差，即一个等差数列，减去改值。

设右边堆的和为rs，左边卫ls

则max（rs-ls）=max（rs*2-（rs+ls））=max（rs*2-sum）

min：2*(i*left+i*(i-1)/2)-sum;

情况同上

3.区间给定，但是取值是以step为2来间隔区的，所以，（（B-A）-min）%2=0，才会输出possible，否则为not possible。

#include

using namespace std;

int N;

void process(int A,int B,int lf,int rg)

{

int diff = (A > B) ? (A - B) : (B -A) ;

int sum=0;

int N=rg-lf+1;

for(int i=lf;i<=rg;i++)

{

sum+=i;

}

if(diff == sum) {cout<<"possible"<

for(int i=1;i

{

int maxx=2*(i*rg-i*(i-1)/2)-sum;

int minn=2*(i*lf+i*(i-1)/2)-sum;

if(diff<=maxx&&diff>=minn&&((diff-minn)%2==0))

{cout<<"possible"<

}

cout<<"not possible"<

}

int main()

{

cin>>N;

int A,B;

int lf,rg;

for(int i=1;i<=N;i++)

{

cin>>A>>B>>lf>>rg;

process(A,B,lf,rg);

}

return 0;

}

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29172126/viewspace-774279/ ，如需转载，请注明出处，否则将追究法律责任。

上一篇：网页爬虫——图论

下一篇：火车运煤问题

请登录后发表评论登录

全部评论

晚秋的枫叶

注册时间：2013-09-12

博文量
4
访问量

5828

ITPub博客

sicily1047__Super Snooker

最新文章