ITPub博客

首页 > Linux操作系统 > Linux操作系统 > sicily1047__Super Snooker

sicily1047__Super Snooker

原创 Linux操作系统 作者:晚秋的枫叶 时间:2013-10-13 11:12:47 0 删除 编辑
题目链接: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博客 ” ,链接:http://blog.itpub.net/29172126/viewspace-774279/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 火车运煤问题
请登录后发表评论 登录
全部评论

注册时间:2013-09-12

  • 博文量
    4
  • 访问量
    5143