版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434634
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
有点考想象力,物理竞赛题,呵呵。思路:
两个球发生碰撞,可以看成擦肩而过(不损失任何能量),接着计算指定高度到地面所需要花费的时间,求得返回次数,如果返回次数为偶数,说明小球处于下落态,用下落公式求解即可。如果奇数呢?说明小球上升态,可以看成下落态用同一公式求解,真是会玩。
公式:
y=H−12⋅g⋅(T−k⋅t)2
y = H - \frac{1}{2}\cdot g \cdot (T - k\cdot t)^2
上升的公式可以自己推一推,不难。
代码如下:
void solve() {
int n = ni();
while (n-- > 0){
int N = ni();
int H = ni();
int R = ni();
int T = ni();
double[] ans = new double[N];
for (int i = 0; i < N; ++i){
ans[i] = calc(T - i, H);
}
Arrays.sort(ans);
for (int i = 0; i < N; ++i){
out.printf("%.2f%c",ans[i] + 2 * R * i / 100.0, (i + 1 == N ? '\n' : ' '));
}
}
}
double calc(int T, int H){
if (T < 0) return H;
double t = Math.sqrt(2.0 * H / 10.0);
int k = (int) (T * 1.0 / t);
if (k % 2 == 0){
double d = k * t;
return H - 0.5 * 10.0 * (T - d) * (T - d);
}
else{
double d = k * t + t;
return H - 0.5 * 10.0 * (T - d) * (T - d);
}
}
问想象力有多重要!直接给思路:
首先想象整个世界只有一只蚂蚁,于是可以计算出爬行时间最长的那一只,把它记下来。接着考虑其他蚂蚁,碰头时想象为两只蚂蚁交换姓名,擦肩而过即可。那么问题就剩下,统计这只蚂蚁跟多少只蚂蚁交换了姓名,最后交换的那一只就是答案了。那么到底跟谁交换了姓名呢?由于蚂蚁速度都一样,于是在前进路线上只会与那些逆行的蚂蚁碰头。统计出来后问题就解决了,需要注意答案的格式是截断小数不是四舍五入。
参考:http://www.hankcs.com/program/algorithm/poj-2674-linear-world.html
起初我在纠结算出那只走过最长距离的蚂蚁名字后,该怎么进行交换,结果呵呵哒了,统计和它反向的次数,并在原来基础上相加。
比如:
p n n p p n
0 1 2 3 4 5
index = 0
可以得出一个结论,相邻两只反向蚂蚁,一定会碰撞,所以45位置的蚂蚁会反向一次,所以可以看成如下:
p n n p n p
一旦发生了碰撞,4位置的蚂蚁的方向发生了变化,名字还是4,既然如此,还可以继续传递:
p n n n p p
在这里可以发现一个规律,所有的n排在了p的右侧,而p全部跑到了右侧。
其实可以想象:
a. 任何相邻的两个小球发生碰撞,它们的次序不会发生变化(空间位置),因为碰撞后朝反方向走,真实情景中,它们的次序可以看作没有变化。
所以,对于任意球的碰撞,我们传递的无非是它们的撞击方向,碰撞一次,n变p,p变n,所以有了上面的尝试,而神奇的是:
经过长时间的碰撞后,会趋于一种稳定态,即 n n n p p这种事件,现在与第一个p发生最后一次碰撞的位置就显而易见了。
代码如下:
static class Inhabitant{
char direction;
String name;
double pos;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true){
String line = in.nextLine().trim();
int n = Integer.parseInt(line);
if (n == 0) break;
line = in.nextLine();
String[] nums = line.trim().split(" +");
double l = Double.parseDouble(nums[0]);
double v = Double.parseDouble(nums[1]);
Inhabitant[] ants = new Inhabitant[n];
for (int i = 0; i < n; ++i){
ants[i] = new Inhabitant();
line = in.nextLine();
nums = line.trim().split(" +");
ants[i].direction = Character.toLowerCase(nums[0].charAt(0));
ants[i].name = nums[2];
ants[i].pos = Double.parseDouble(nums[1]);
}
Arrays.sort(ants, new Comparator<Inhabitant>() {
@Override
public int compare(Inhabitant o1, Inhabitant o2) {
double pos1 = o1.pos;
double pos2 = o2.pos;
return pos1 < pos2 ? -1 : 1;
}
});
double maxDistance = 0.0;
int index = 0;
boolean forward = true;
for (int i = 0; i < n; ++i){
if(ants[i].direction == 'n'){
if(ants[i].pos > maxDistance){
maxDistance = ants[i].pos;
index = i;
forward = false;
}
}
else{
if ((l - ants[i].pos) > maxDistance){
maxDistance = l - ants[i].pos;
index = i;
forward = true;
}
}
}
if(forward){
int cnt = 0;
for (int i = index; i < n; ++i){
if (ants[i].direction == 'n') cnt++;
}
index += cnt;
}
else{
int cnt = 0;
for (int i = index; i >= 0; --i){
if(ants[i].direction == 'p') cnt++;
}
index -= cnt;
}
double result = maxDistance / v;
System.out.printf("%13.2f %s\n",(int) (result * 100) / 100.0, ants[index].name);
}
in.close();
}
轻松一下,注意下是所有蚂蚁落杆的最少时间。
代码如下:
void solve() {
int c = ni();
while (c --> 0){
int l = ni();
int n = ni();
int[] ants = na(n);
int min = 0, max = 0;
for (int i = 0; i < n; ++i){
min = Math.max(min, Math.min(ants[i], l - ants[i]));
max = Math.max(max, Math.max(ants[i], l - ants[i]));
}
out.println(min + " " + max);
}
}