本题 由 Red 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
严禁抄袭,侵权必究。代码仅当参考使用。
第2题
描述
世人皆好奇lxy的体重,但lxy自己不愿意说,她由两个舍友lwj和knt表示可以透露lxy的体重,但不会直接说出数值。目前已知lxy的体重是1到300斤之间的某个整数(包括1和300)。
lwj喜欢透露lxy的体重除以a的余数等于b,knt喜欢透露lxy的体重大于d或者小于d。当她们透露了一定的消息以后,就可以唯一确定lxy的体重,当然也有可能因为自相矛盾而导致无解,也有可能有多个可能的解。
现有lwj和knt的一系列透露的消息,分别是lwj一句话knt一句话这样的循环,想知道最终是否能够确定lxy的体重。
输入
只有一组测试案例。
第1行是一个正整数n,表示lwj和knt一共透露了多少句话(两个人说话的总和)
第2到第n+1行是她们说的n句话,其中第偶数行是lwj说的,每行包括两个整数a、b(a>b>=0),表示lxy的体重除以a的余数等于b。第奇数行是knt说的,每行包括两个整数c和d(c只会是1或者-1,d>=0),如果c=1,表示lxy的体重大于d;如果c=-1,则表示lxy的体重小于d。
输出
如果根据她们说的n句话,lxy的体重是无解的,则输出-1;如果lxy的体重有多个合法的解,则输出0;如果lxy的体重有唯一解,则输出体重值。不要换行。
样例输入
4
12 0
1 110
10 0
-1 130
样例输出
120
提示说明
4句话分别代表体重除以12余0,体重大于110,体重除以10余0,体重小于130,故可以断定lxy的体重是120
思路
一般的思路是很直观的,那就是将所有数读进一个数组后再在knt提供的最小和最大数之间进行遍历,挨个判断余数是否相符就行
但事情并没有这么简单,你会发现在还没学二维数组之前,你很难将lwj提供的数据储存起来再参与到余数判断的遍历中(当然也有办法)
所有一般的思路永远没有二般的好用,下面就来介绍一下
结合对余数的理解,可以用累加的方式,从b开始,每次加a加到<=300为止。又因为一共有(n+1)/2行的要求,所有符合这个要求的数就是满足条件,在计数器cnt中就能+1了
需要注意的是,在判断“体重无解”或“体重有解”后要及时跳出程序,否则会出现多次输出的情况。具体操作就是在满足条件的最后都加上break
代码[C++]
[Forlogin]
#include<iostream>
#include<limits.h>
using namespace std;
int main()
{
int n,i=2,wight[301]={0},min=1,max=300,cnt=0,k[2]={0},md=0;
cin>>n;
while(i<=n+1){
if(i%2==0){
int a,b;
cin>>a>>b;
for (int j=b;j<=300;j+=a) wight[j]++;
}else{
int c,d;
cin>>c>>d;
if(c==1&&d>min) min=d;
if(c==-1&&d<max) max=d;
if(max<=min) {cout<<"-1";md=1;break;}
}
i++;
}if(md!=1){
for (int j=min;j<=max;j++){
if(wight[j]==(n+1)/2){
k[0]=j;
cnt++;
if(cnt>1){
cout<<"0";
break;
}
}
}
if(cnt==0) cout<<"-1";
if(cnt==1) cout<<k[0];
}
return 0;
}[/Forlogin]
题外话
这题卡了超久