2057. [ZLXOI2015]殉国-白红宇

2057. [ZLXOI2015]殉国

阅读量：5763 次

发布时间：2019-06-18

本文共 2056 字，大约阅读时间需要 6 分钟。

★☆ 输入文件：BlackHawk.in 输出文件：BlackHawk.out 评测插件

时间限制：0.05 s 内存限制：256 MB

【题目描述】

正义的萌军瞄准了位于南极洲的心灵控制器，为此我们打算用空袭摧毁心灵控制器，然而心灵控制器是如此强大，甚至能缓慢控制飞行员。一群勇敢的士（feng）兵（zi）决定投弹后自杀来避免心灵控制。然而自杀非常痛苦，所以萌军指挥官决定到达目的地后让飞机没油而坠落(也避免逃兵)。军官提供两种油：石油和中国输送来的地沟油,刚开始飞机没有油，飞机可以加几桶石油和几桶地沟油(假设石油和地沟油都有无限桶)，飞机落地时必须把油耗尽，已知一桶石油和一桶地沟油所能支撑的飞行距离分别为a,b,驾驶员们必须飞往一个目的地，总距离为c.

1.最少，最多需要加几桶油，若只有一种方案，最少和最多的是相同的.

2.总共有多少种不同的加油配方(死法)能到达目的地。

【输入格式】

只有一行，三个正整数a,b,c

【输出格式】

两行，第一行为最少加几次油和最多加几次油，

第二行为加油方法总数。

若不存在任何方法，第一行输出-1 -1

第二行输出0

【样例输入】

样例1：2 3 10样例2：6 8 10

【样例输出】

样例1：4 52样例2：-1 -10

【提示】

样例解释：

样例一：飞机加两次石油，两次地沟油，总次数为4，2*2+3*3=10

飞机加五次石油，不加地沟油，总次数为5,2*5+3*0=10

总共两种

样例二：飞机无法到达目的地

数据范围：

对于10%的数据,

对于20%的数据,

对于50%的数据，

对于100%数据，

三个答案分值权重分别为20%,30%,50%

【来源】

这个题就是个扩展欧几里得的裸题，也不算太裸，因为涉及到求最小值和最大值的问题

但是自己写了一个交上去爆零，后来看了看比人写的代码，发现还是懵逼在45—49行里。。

4546貌似是求最大区间，，但是为什么要/b/a呢？x为什么要加负号呢？？

还有ans1，ans2的b-a是什么鬼。。

啊啊啊啊啊啊为什么为什么为什么。。。。。。

=.=

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
           7 #define LL long long 8 using namespace std; 9 LL a,b,c,x,y;10 LL read(LL & n)11 {12 int flag=0,x=0;char c='/';13 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}14 while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();15 if(flag)n=-x;16 else n=x;17 }18 LL gcd(LL a,LL b)19 {20 if(b==0)return a;21 else return gcd(b,a%b);22 }23 LL exgcd(LL a,LL b,LL &x ,LL & y)24 {25 if(b==0)26 {x=1;y=0;return a;}27 LL r=exgcd(b,a%b,x,y);28 LL tmp=x;x=y;y=tmp-(a/b)*y;29 return r;30 }31 int main()32 {33 //freopen("BlackHawk.in","r",stdin);34 //freopen("BlackHawk.out","w",stdout);35 //read(a);read(b);read(c);36 cin>>a>>b>>c;37 LL p=gcd(a,b);38 if(c%p!=0)39 {40 printf("-1 -1\n0");41 return 0;42 }43 exgcd(a,b,x,y);44 // printf("%d %d",x,y);45 LL xx=ceil((long double)-x/b*c);46 LL yy=floor((long double)y/a*c);47 LL ans=yy-xx+1;48 LL ans1=x*c/p+y*c/p+(b-a)/p*yy;49 LL ans2=x*c/p+y*c/p+(b-a)/p*xx;50 if(ans<=0) printf("-1 -1\n0");51 else cout<
           
            <<" "<
            
             <
             
              <

转载地址：http://qogkx.baihongyu.com/

你可能感兴趣的文章