首页 > ACM题库 > HDU-杭电 > HDU 3921-Clear All of Them II-贪心-[解题报告]HOJ
2015
04-14

HDU 3921-Clear All of Them II-贪心-[解题报告]HOJ

Clear All of Them II

问题描述 :

Acmers have been the Earth Protector against the evil enemy for a long long time, now it’s your second turn to protect our home.
  There are 4 * n enemies in the map. Your task is to clear all of them with your super laser gun at the fixed position (x, y).
  For each laser shot, your laser beam can reflect 3 times (must be 3 times), which means it can kill 4 enemies at one time. And the energy this shot costs is the total length
of the laser path.
For example, if you are at (0, 0), and use one laser shot kills the 4 enemies in the order of (3, 4), (6, 0), (3, 0), (0, 4), then the energy this shot costs is 5.0 + 5.0 + 3.0 + 5.0
= 18. 00.
To save the energy, you decide to use the Greedy Algorithm, which means for each shot, you select four existed enemies and decide the reflect order, so that this shot’s
energy cost is minimum. If there is a tie, we assure that choosing the shot whose four enemies’ average distance to you is smallest can avoid a tie. (See the sample for
more details)
Now, telling you your position and the 4n enemies’ position, can you tell me how much energy you need in total to clear all of them?
  Note that:
   > Each enemy can only be attacked once.
   > All the positions will be unique.
   > You must attack 4 different enemies in one shot.
   > You can’t change your position.

输入:

The first line contains a single positive integer T( T <= 20 ), indicates the number of test cases.
For each case:
  There are 2 integers x and y in the first line, which means your position.
  The second line is an integer n(1 <= n <= 50), denote there are 4n enemies.
  Then there following 4n lines, each line have 2 integers denote the position of an enemy.
  All the position integers are between -1000 and 1000.

输出:

The first line contains a single positive integer T( T <= 20 ), indicates the number of test cases.
For each case:
  There are 2 integers x and y in the first line, which means your position.
  The second line is an integer n(1 <= n <= 50), denote there are 4n enemies.
  Then there following 4n lines, each line have 2 integers denote the position of an enemy.
  All the position integers are between -1000 and 1000.

样例输入:

2

0 0
1
6 0
3 0
3 4
0 4

0 0
2
1 0
2 0
3 0
4 0
1 1
1 2
1 3
1 4

样例输出:

Case #1: 14.00
Case #2: 13.00

Hint
Case #2: For the first shot, (0, 0)->(1, 0)->(2, 0)->(3, 0)->(4, 0) cost 4 energy; and (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3) cost 4 energy, too. But (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3)’s average distance to you(0, 0) is smallest(which is about 1.9531398), so we choose (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3) for the first shot.

4*n个点,每次选4个点,使得距离(射击点—1—2—3—4)最短。问最终将所有点都选完的最小距离

题目给了一个贪心策略,在时间允许范围内搜索即可

枚举任意两点b和c,计算出距离b和距离射击点距离之和最小的点tmp1和次小的点tmp12(并且该点当前未被访问并且不是b c点),再计算出距离c最短的和次短的点tmp2,tmp22,然后更新操作.(分tmp1 == tmp2 和 tmp1 != tmp2两种情况讨论, 求次小是为了tmp1 == tmp2这种情况)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define EPS 1e-4
const int MAXN = 201;
int n;
double ans,mi;
struct Point{
		double x,y;
		void input(){
				scanf("%lf%lf",&x,&y);
		}

}ps[MAXN],o;
inline double pdis(Point a,Point b){
		return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int flag[MAXN];
int minodis[MAXN][MAXN];
int mindis[MAXN][MAXN];
double odis[MAXN];
double ppdis[MAXN][MAXN];
int si,ssi,o1,o2,o3,o4;
inline int cmp1(int a,int b){
		return ppdis[a][si] + EPS < ppdis[b][si];
}
inline int cmp2(int a,int b){
		return ppdis[a][ssi] + odis[a] + EPS < ppdis[b][ssi] + odis[b];
}

inline void update(int p1,int p2,int p3,int p4){
	
		double tmp = odis[p1] + ppdis[p1][p2] + ppdis[p2][p3] + ppdis[p3][p4];
		if(tmp+EPS < mi){
			mi = tmp;
			o1 = p1;o2 = p2;o3 = p3;o4 = p4;
		}
		else if(fabs(tmp-mi) < EPS){
			if(odis[p1]+odis[p2]+odis[p3]+odis[p4] < odis[o1]+odis[o2]+odis[o3]+odis[o4]){
				o1 = p1;o2 = p2;o3 = p3;o4 = p4;
			}
		}
}
int main(){
		int cas;
		scanf("%d",&cas);
		for(int kcas = 1; kcas <= cas; ++kcas){
				o.input();
				scanf("%d",&n);
				n = 4*n;
				for(int i = 0; i < n; ++i)ps[i].input();
				for(int i = 0; i < n; ++i){
						odis[i] = pdis(o,ps[i]);
						for(int j = 0; j < n; ++j){
								ppdis[i][j] = pdis(ps[i],ps[j]);
						}
				}
				for(int i = 0; i < n; ++i){
						int cnt = 0;
						for(int j = 0; j < n; ++j){
								if(i == j)continue;
								mindis[i][cnt] = j;
								minodis[i][cnt++] = j;
						}
						si = i;ssi = i;
						sort(mindis[i],mindis[i]+cnt,cmp1);
						sort(minodis[i],minodis[i]+cnt,cmp2);
				}
				ans = 0.0;
				memset(flag,0,sizeof(flag));
				int tmpn = n/4;
				while(tmpn --){
					mi = 1e100;
					for(int i = 0; i < n; ++i){
						if(flag[i])continue;
						for(int j = 0; j < n; ++j){
								if(i == j)continue;
								if(flag[j])continue;
								int t = 0;
								while ((minodis[i][t] == i || minodis[i][t] == j ||flag[minodis[i][t]]))t++;
								int tmp1 = minodis[i][t];
								t++;
								while (minodis[i][t] == i || minodis[i][t] == j ||flag[minodis[i][t]])t++;
								int tmp12 = minodis[i][t];

								t = 0;
								while ((mindis[j][t] == i || mindis[j][t] == j || flag[mindis[j][t]]))t++;
								int tmp2 = mindis[j][t];
								t++;
								while (mindis[j][t] == i || mindis[j][t] == j || flag[mindis[j][t]])t++;
								int tmp22 = mindis[j][t];
								double tmp;
								if(tmp1 == tmp2){
										update(tmp12,i,j,tmp2);
										update(tmp1,i,j,tmp22);
										continue;
								}
								
								update(tmp1,i,j,tmp2);
						}
					}
					ans += mi;
					flag[o1] = flag[o2] = flag[o3] = flag[o4] = 1;
				//	printf("%d %d %d %d\n",o1,o2,o3,o4);
				}
				printf("Case #%d: ",kcas);
				printf("%.2lf\n",ans);
		}
		return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/accry/article/details/6677731


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。