PKU ACM 1852、3684解题报告
之所以把这两道题放到一起，是因为这两道题是同一种题型，我把它们叫做“穿越题”。解这种题型的题目，关键是要用穿越的思想。一般这种题目，如果不能想进去的话，会感觉无从下手，可一旦想进去，就会发现题目太简单了。
解1852时，关键是要看出，就算两只蚂蚁相遇各自会朝相反方向移动，但如果我们假设相遇的蚂蚁依然能按照原来的方向移动，即它们穿越了对方的身体，这样问题就简单多了，而且，这样的假设，对最后的答案并没有影响。
同样地，在题3684中，我们也可以假设，两个球相互碰撞时，它们也穿越了对方的球体，依然朝着原来的方向运动，这时，我们就可以忽略其他球，把每个球当做一个个独立的球体，它们之间的运动不受其他球的影响，这样问题也就变得很简单了，而且，这样做并不影响最后的结果，不过最后得再对这些球的位置进行一次排序，因为这些球的相对位置关系是固定的。
Code:
1852:
/*
*题目出处：http://poj.org/problem?id=1852 Ants
*解题思路:假设蚂蚁能各自穿过其他蚂蚁的身体，这并不影响最短和最长时间的计算
*Status: Accepted
*author：Jorbe
*date: 2013.11.28
*/
#include <iostream>
#define max 1000000
using namespace std;
int get_min(int a,int b)
{
return a<b?a:b;
}
int get_max(int a,int b)
{
return a>b?a:b;
}
void solve(int* x,int L,int n)
{
int min_time=0;
for(int j=0;j<n;j++)
{
min_time=get_max(min_time,get_min(x[j],L-x[j]));
}
int max_time=0;
for(int k=0;k<n;k++)
{
max_time=get_max(max_time,get_max(x[k],L-x[k]));
}
printf("%d %d\n",min_time,max_time);
}
int main()
{
int N;
cin>>N;
while(N--)
{
int L,n;
int x[max];
int i;
cin>>L>>n;
for(i=0;i<n;i++)
{
cin>>x[i];
}
solve(x,L,n);
}
return 0;
}
3684:
/*
*题目出处：http://poj.org/problem?id=3684 Physics Experiment
*解题思路:一道“穿越题”，只要能想到球实际上可以穿越，并不影响最后结果，题目就简单多了
*Status: Accepted
*author：Jorbe
*date: 2014.01.25
*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define max 100
const double g=10.0;
//输入
int N,H,R,T;
int C;
double y[max];
double cal(int T) //T时刻球的位置
{
if(T<0) return H;
double t=sqrt(2*H/g); //从H处下落到地面需要的时间
int k=(int)(T/t);
if(k%2==0)
{
double d=T-k*t;
return H-g*d*d/2;
}else{
double d=k*t+t-T;
return H-g*d*d/2;
}
}
void solve()
{
for(int i=0;i<N;i++)
{
y[i]=cal(T-i);
}
sort(y,y+N); //对N球的位置按竖直方向进行排序
for(int j=0;j<N;j++)
{
printf("%.2f%c",y[j]+2*R*j/100.0,j+1==N?'\n':' ');
}
}
int main()
{
cin>>C;
while(C--)
{
cin>>N>>H>>R>>T;
solve();
}
return 1;
}