Description
Input
第1行为一个整数N(1<=N<=15)，即野人的数目。第2行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。
Output
仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于106。
看到这题，我们想到了bzoj 1477 青蛙的约会。
但是我们发现l的值不确定。。所以我们使用枚举大发。。
直接从scanf的最大编号开始枚举L,然后枚举两个野人，看他们的ax+by=n是否无解或解小于min(life[i],life[j])，如果是的话，继续，不是则break(与题目条件冲突，ax+by=n是什么可以看看我之前写的青蛙的约会的题解，不加berak会TLE)
上代码吧。。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 6 using namespace std; 7 8 int x,y,l[16],str[16],h[16]; 9 10 int exgcd(int n,int m) 11 { 12 if(m==0){x=1,y=0;return n;} 13 int ans=exgcd(m,n%m),t=x; 14 x=y,y=t-n/m*y; 15 return ans; 16 } 17 18 bool judge(int aa,int bb,int m) 19 { 20 int a=h[aa]-h[bb],b=m,c=str[bb]-str[aa]; 21 int g=exgcd(a,b); 22 if(c%g!=0){return 0;} 23 a/=g,b/=g,c/=g; 24 b=fabs(b); 25 exgcd(a,b); 26 int ans=((x*c)%b+b)%b; 27 if(!ans)ans+=m; 28 if(ans<=min(l[aa],l[bb]))return 1; 29 return 0; 30 } 31 32 int main() 33 { 34 int n,mx=0; 35 scanf("%d",&n); 36 for(int i=1;i<=n;i++){scanf("%d%d%d",&str[i],&h[i],&l[i]);mx=max(mx,str[i]);} 37 for(mx;;mx++) 38 { 39 bool flag=1; 40 for(int i=1;i<=n&&flag;i++) 41 for(int j=i+1;j<=n&&flag;j++) 42 if(judge(i,j,mx))flag=0; 43 if(flag){printf("%d",mx);return 0;} 44 } 45 }