1400 - 奥运排序问题
时间限制 : 1 秒
内存限制 : 32 MB
按要求，给国家进行排名。
题目输入
有多组数据。
第一行给出国家数N，要求排名的国家数M，国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数，奖牌数，人口数（百万）。
接下来一行给出M个国家号。
题目输出
排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例
对每个国家给出最佳排名排名方式 和 最终排名
格式为: 排名:排名方式
如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例
如果有并列排名的情况，即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.
每组数据后加一个空行。
输入/输出样例
输入格式
4 4 4 8 1 6 6 2 4 8 2 2 12 4 0 1 2 3 4 2 8 10 1 8 11 2 8 12 3 8 13 4 0 3
输出格式
1:3 1:1 2:1 1:2 1:1 1:1
C语言解答
#include <stdio.h> #include <malloc.h> typedef struct Record { int gold; int award; int people; }Record; int sort(Record *recs,int nums[],int M) { for(int i=0;i<M;i++) { int rank[4]; rank[0]=M; rank[1]=M; rank[2]=M; rank[3]=M; for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).gold>=(*(recs+nums[j])).gold) { rank[0]--; } } for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).award>=(*(recs+nums[j])).award) { rank[1]--; } } for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).gold/(float)((*(recs+nums[i])).people)>=(*(recs+nums[j])).gold/(float)((*(recs+nums[j])).people)) { rank[2]--; } } for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).gold/(float)((*(recs+nums[i])).people)>=(*(recs+nums[j])).gold/(float)((*(recs+nums[j])).people)) { rank[3]--; } } int min=rank[0];int minp=0; for(int i=1;i<4;i++) { if(min>rank[i]) { min=rank[i]; minp=i; } } printf("%d:%d\n",min,minp+1); } printf("\n"); } int main() { while(1) { int N; int M; int nums[200]; if(scanf("%d",&N)==EOF) { break; } scanf("%d",&M); Record* recs=(Record*)malloc(N*sizeof(Record)); for(int i=0;i<N;i++) { scanf("%d",&((*(recs+i)).gold)); scanf("%d",&((*(recs+i)).award)); scanf("%d",&((*(recs+i)).people)); } for(int i=0;i<M;i++) { scanf("%d",&nums[i]); } sort(recs,nums,M); } }
C++解答
#include <stdio.h> #include <algorithm> using namespace std; struct Nation{ // 国家信息结构类型 int num; // 国家编号 double orderValue[4]; // 用来排名的值 int order[4]; // 名次 }; Nation na[100000]; // 存储国家信息 bool cmp0(Nation a,Nation b){ // 按国家编号排名 return a.num < b.num; } bool cmp1(Nation a,Nation b){ // 按金牌数排名 return a.orderValue[0] > b.orderValue[0]; } bool cmp2(Nation a,Nation b){ // 按奖牌数排名 return a.orderValue[1] > b.orderValue[1]; } bool cmp3(Nation a,Nation b){ // 按金牌人口比排名 return a.orderValue[2] > b.orderValue[2]; } bool cmp4(Nation a,Nation b){ // 按奖牌人口比排名 return a.orderValue[3] > b.orderValue[3]; } int main(){ #ifndef ONLINE_JUDGE freopen("in", "r", stdin); #endif int n, m; // 用来存储国家总数以及需要排名国家的数目 int gold, total, pop; // 用来读取金牌数、奖牌数以及人口 int need; // 存储需要排名的国家编号数 while(scanf("%d%d", &n, &m) != EOF){ int i; for(i=0; i<n; i++){ // 读入国家信息，并计算金牌人口比以及奖牌人口比 scanf("%d%d%d", &gold, &total, &pop); na[i].orderValue[0] = gold; na[i].orderValue[1] = total; na[i].orderValue[2] = 1.0*gold/pop; na[i].orderValue[3] = 1.0*total/pop; na[i].num = i; } for(i=0; i<m; i++){ // 只存储需要排名的国家 scanf("%d", &need); na[i] = na[need]; } // 按金牌数排名，计算名次 sort(na, na+m, cmp1); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[0]==na[i].orderValue[0]){ na[i].order[0] = na[i-1].order[0]; }else{ na[i].order[0] = i+1; } } // 按奖牌数排名，计算名次 sort(na, na+m, cmp2); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[1]==na[i].orderValue[1]){ na[i].order[1] = na[i-1].order[1]; }else{ na[i].order[1] = i+1; } } // 按金牌人口比排名，计算名次 sort(na, na+m, cmp3); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[2]==na[i].orderValue[2]){ na[i].order[2] = na[i-1].order[2]; }else{ na[i].order[2] = i+1; } } // 按奖牌人口比排名，计算名次 sort(na, na+m, cmp4); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[3]==na[i].orderValue[3]){ na[i].order[3] = na[i-1].order[3]; }else{ na[i].order[3] = i+1; } } // 按国家编号排序，输出结果 sort(na, na+m, cmp0); int j, index; for(i=0; i<m; i++){ index = 0; // 从四种方法中获得最佳结果 for(j=0; j<4; j++){ if(na[i].order[j] < na[i].order[index]){ index = j; } } printf("%d:%d\n", na[i].order[index], index+1); } putchar('\n'); } return 0; }
Java解答
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); while(in.hasNextInt()){ int n=in.nextInt(); int m=in.nextInt(); int[] a=new int[n]; int[] b=new int[n]; int[] c=new int[n]; double[] d=new double[n]; double[] e=new double[n]; for(int i=0;i<n;i++){ a[i]=in.nextInt(); b[i]=in.nextInt(); c[i]=in.nextInt(); d[i]=a[i]*1.0/c[i]; e[i]=b[i]*1.0/c[i]; } int[] a3=MM(a); int[] b3=MM(b); int[] d3=MM(d); int[] e3=MM(e); for(int h=0;h<m;h++){ int g=in.nextInt(); int y=MMM(a3[g],b3[g],d3[g],e3[g]); if(a3[g]==y) {System.out.println(y+":"+1);continue;} if(b3[g]==y) {System.out.println(y+":"+2);continue;} if(d3[g]==y) {System.out.println(y+":"+3);continue;} if(e3[g]==y) {System.out.println(y+":"+4);continue;} } System.out.println(); } } public static int[] MM(int[] a) { int[] a1 =new int[a.length]; int max=0,j,s=0,count=1; while(Mm(a)){ max=0; for(j=0;j<a.length;j++) if(a[j]>max) max=a[j]; for(int k=0;k<a.length;k++) if(a[k]==max) {s++;a1[k]=count;a[k]=-1;} count=s+1; } return a1; } public static int[] MM(double[] a) { int[] a1 =new int[a.length]; double max=0; int j,s=0,count=1; while(Mm(a)){ max=0; for(j=0;j<a.length;j++) if(a[j]>max) max=a[j]; for(int k=0;k<a.length;k++) if(a[k]==max) {s++;a1[k]=count;a[k]=-1.0;} count=s+1; } return a1; } public static boolean Mm(int[] a) { for(int i=0;i<a.length;i++) if(a[i]>=0) return true; return false; } public static boolean Mm(double[] a) { for(int i=0;i<a.length;i++) if(a[i]>=0) return true; return false; } public static int MMM(int a,int b,int c,int d){ int min=a; if(min>b) min=b; if(min>c) min=c; if(min>d) min=d; return min; } }