swustoj 1164: 导弹拦截之升级版

swustoj 1164: 导弹拦截之升级版

题目描述：

由于开始那个拦截系统太水、So..... 经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径R。某天，雷达捕捉到敌国的导弹来袭,来袭导弹数目为N，导弹距离拦截系统的距离分别为a1,a2,a3,........,aN。最后所有成功拦截的导弹距离之和用S表示。而当天的使用代价用V表示，且V=R*N-S。请计算V最小时，R应该为多少？ 为了向民众交代，至少成功拦截一枚导弹，如果R有多个解，只保留最大的一个。

Input:

多组测试数据；
对于每组数据共有两行：
第一行一个N（N<=1000），表示导弹个数；
第二行N个数，表示每颗导弹的到拦截系统的距离ai(0<=ai<=30000，整数)，以空格隔开 。

Output:

每组数据一行，输出当V最小时，R的值。

样例输入：                                                                                        样例输出：

3                                                                                                          250

100 200 250

输出结果需要 rn换行

解题思路：

        首先将导弹距离从小到大排序（至少拦截一枚导弹），分别计算出每次拦截需要的成本，比较最小值，输出即可（如有相同输出最大的半径）。

C++代码1（直接比较每次结果）：

#include<bits/stdc++.h>
using namespace std;
int main(void)
{int n;while(cin>>n){int num[1000];for(int i=0;i<n;i++)cin>>num[i];sort(num,num+n);//从小到大排序 int min=num[0]*n-num[0];//至少拦截第一枚导弹int sum=0,key=0;//sum表示距离之和,key表示导弹半径下标 for(int i=0;i<n;i++){sum+=num[i];if(num[i]*n-sum<=min){min=num[i]*n-sum;key=i;}}printf("%drn",num[key]);}return 0;
}

C++代码2（将每次结果存入数组再比较）：

#include<bits/stdc++.h>
using namespace std;
int main(void)
{int n;while(cin>>n){int num[1000];for(int i=0;i<n;i++)cin>>num[i];sort(num,num+n);//从小到大排序 int v[1000]={0}; int sum=0,key=0;//sum表示距离之和,key表示导弹半径下标 for(int i=0;i<n;i++){sum+=num[i];v[i]=num[i]*n-sum;}int minv=num[n-1]*n;for(int i=0;i<n;i++)minv=min(minv,v[i]);for(int i=n-1;i>=0;i--)if(minv==v[i]){printf("%drn",num[i]);break;}}return 0;
}

思路和代码仅供参考，欢迎各位大佬提出意见和建议。