社区讨论

除了三个超时的剩下的全部都过了

P1158[NOIP 2010 普及组] 导弹拦截参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo9jnh51
此快照首次捕获于
2023/10/28 12:30
2 年前
此快照最后确认于
2023/10/28 12:30
2 年前
查看原帖
CPP
#include <stdio.h>
#include <math.h>
long long result=9999999999999,qaq[110000],qwq[110000],xiabiao[110000];
long long juli(long long x1, long long y1, long long x2, long long y2)
{
	long long len=((x1-x2)* (x1 - x2) + (y1 - y2)*(y1-y2));	
	return len;
}
long long main()
{
	long long n,x1, y1, x2, y2;
	scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
	scanf("%lld", &n);
	long long x=0, y=0,q,p;
	for (long long i = 0; i < n; i++)
	{
		scanf("%lld%lld", &x, &y);
		qaq[i] = juli(x1, y1, x, y);//到1
		//尝试保存下标
		xiabiao[i] = i;
		qwq[i] = juli(x2, y2, x, y);//到2
	}
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (qaq[i] < qaq[j])
			{
				int tem = qaq[i];
				qaq[i] = qaq[j];
				qaq[j] = tem;
				int s = qwq[i];
				qwq[i] = qwq[j];
				qwq[j] = s;
			}//排序,使得两组数据始终对应相等
		}//qaq是所有导弹到第一个系统的距离数组,qaq是所有导弹到第二个系统的距离数组
	}
	//qaq已经升序了
	int max = 0,sum=0;
	for (int i = 0; i < n; i++)
	{
		sum = 0;
		int j = i - 1;
		if(j>=0)//防止刚开始的时候j是-1
			if (qwq[j] > max)
				max = qwq[j];//更新最大值		
		sum = max + qaq[i];
		if (sum < result)
			result = sum;
	}
	printf("%lld", result);
	return 0;
}


个人感觉是排序方面花时间太多了,第二个样例有十万个数据,选择排序好像有点吃不消

回复

5 条回复,欢迎继续交流。

正在加载回复...