C语言之鹊桥相会

题目描述

一年一度的七夕又要到了，可歌可泣的牛郎织女又可以在鹊桥相会了。不知道大家有没有雅兴陪 Redraiment 坐在葡萄藤下倾听他们的对话。 我们知道，牛郎要与织女相见，必须要有喜鹊搭桥。所以，牛郎必须在天河岸上等待，直到有喜鹊经过，于是牛郎可以搭乘这只喜鹊往河对岸走。当然，牛郎急着去见织女，所以在途中，如果有速度更快的喜鹊赶上了他，他就会换乘那只速度更快的喜鹊。 我们可以假定喜鹊的速度是恒定不变的，并且喜鹊一直是沿直线飞行的（不转弯，更不回头），牛郎坐上喜鹊所花的时间忽略不计。 现给出天河的宽度、每只喜鹊的初始位置（我们设牛郎所在位置为 0，天河方向为正方向）以及它们的速度（有可能是负数，代表喜鹊往反方向飞行），这些数据都是整数。请你来帮忙计算一下牛郎到达对岸与织女相会最少需要多少时间，让他们早些有情人终成眷属。^_^ 当然，如果没有喜鹊来搭载牛郎，我们可怜的牛郎就到不了对岸与织女相会了，那我们只好很遗憾的跟牛郎说：Can't Solve，我们祈祷不要发生这样的事情。

输入

第一行有两个数据 w,n分别代表天河的宽度（单位：km）和喜鹊的只数（1≤w≤1000,1≤n≤10000）。
接下来从第二行到第 n+1 行每行都有两个数据 t,v分别代表 1 只喜鹊的初始位置（单位：mmm）和它的飞行速度（单位：m/s）（−1000≤t≤1000,−100≤v≤100）。 所有的数据范围都不会超过 32 位整数的表示范围（用int型数据不会溢出）。
输入以 0 0结束。

输出

如果牛郎能到达对岸输出他到达对岸所花的总时间（结果精确到秒即可，小数部分舍去），否则输出Can't Solve。

输入 1 1 0 1 0 0 输出 1000

#include <stdio.h> int main() { int w, n; while (scanf("%d %d", &w, &n) == 2) { if (w == 0 && n == 0) break; long long width_m = w * 1000LL; long long min_time = -1; // 用-1表示还没找到有效的喜鹊 for (int i = 0; i < n; i++) { long long t, v; scanf("%lld %lld", &t, &v); // 只有 t <= 0 且 v > 0 的喜鹊才有可能被牛郎坐上并带到对岸 if (t <= 0 && v > 0) { // 到达对岸的时间 = (width_m - t) / v long long time = (width_m - t) / v; if (min_time == -1 || time < min_time) { min_time = time; } } } if (min_time == -1) { printf("Can't Solve\n"); } else { printf("%lld\n", min_time); } } return 0;

if (min_time == -1 || time < min_time) {
min_time = time;

}

//上述if条件这样写是因为输入第一行时time<min_time是不可能的，所以输入的第一行是以min_time=-1来判断的，所以一定会执行min_time=time;下一次再输入第二行时如果时间比第一次输入的时间更少，则就以这个时间为主。

主要是第一行输入的数据计算出来的时间一定要被记录下来，这样才能和第二行输入的数据得出的时间比较，找出最短时间到达对岸。这也是为什么要写上述条件来判断的原因。第一个条件只在第一行输入中用，第二个条件除了第一行输入以外，其他行的判断条件。但二者的最后运行结果是一样的，所以可以写到一个if条件里边。

由上述代码可以看出，看似没有考虑中途换乘的问题，实际上已经考虑换乘问题了，只是不需要模拟更简单。

因为牛郎一开始在0位置，假设他要乘坐一只初始位置为0的喜鹊，这样可以不用考虑离他位置远的喜鹊飞过来，他需要等的时间，那乘坐位置为0但速度慢的喜鹊，一定会被一开始离他远但速度快的喜鹊追上，这时候就要换乘，此时离得近但慢的喜鹊和离得远但快的喜鹊运动的时间是一样的，换乘之后，速度就是离得远但快的喜鹊走到对岸需要的时间，所以这样看来，直接等价成离得远但速度最快的喜鹊从原位置到对岸所有的时间即可，即是最短耗时。

所以无论是在原位置还是离得远的位置，只要速度是最快的，就是我们要找的答案。总路程是原位置到对岸的总路程，速度是最快速度，可以直接计算出总时间然后进行比较，即可。

我的思路历程特别麻烦，因为我当时没有考虑到实际上不用模拟中途被其他喜鹊替换的那个过程。我又在代码中模拟了。同时我忘记还有n这个变量了，用的while，其实不好用。这样就不需要定义count了，也就没有后面的if（count==1）这个条件判断了。下面的代码还有逻辑错误，总之题目思考不对。按下述代码思路根本无法往下进行。🆗就这样吧！还要继续加油啊！！！

下面的代码不对哈：

#include<stdio.h> #include<math.h> int main() { int w,n; scanf("%d%d",&w,&n); int t,v; int count=0; int max_v; int ts=0; int a=w*1000; int s=0; int m=0; int tm=0; while(scanf("%d%d",&t,&v)!=EOF){ count++; if(t==0){ max_v=v; if(v>max_v){//此行代码永远不会成立，因为在上面刚赋值max_v=v;所以这里肯定不对。 max_v=v; ts=a/max_v; } } if(t<0&&v>max_v){ t=-t; ts=t/(v-max_v); s=ts*max_v; m=a-s; } max_v=v; tm=ts+m/max_v; } if(count==1&&t==0&&v>0){ tm=a/v; }else if(count==1&&t>0&&v>0||count==1&&t==0&&v<0||count==0){ printf("Cant't Solve"); }else{ printf("%d",tm); } return 0; }