社区讨论
除了三个超时的剩下的全部都过了
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 条回复,欢迎继续交流。
正在加载回复...