浙大PAT 7-06 题解

浙大PAT 7-06 题解

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
#define N 400
#define ll int
using namespace std;
struct node{
 ll gold,all,pre,num;
 double pa,pg;
 ll r1,r2,r3,r4;
 
}p[N];
bool cmp1(node a,node b){return a.gold>b.gold;}
bool cmp2(node a,node b){return a.all>b.all;}
bool cmp3(node a,node b){return a.pa>b.pa;}
bool cmp5(node a,node b){return a.pg>b.pg;}

bool cmp4(node a,node b){return a.num<b.num;}

int main(){
 ll n,m,i,j;
 while(~scanf("%d%d",&n,&m)){
  for(i=0;i<n;i++){
   scanf("%d %d %d",&p[i].gold,&p[i].all,&p[i].pre);
   p[i].num=i;
   
   if(p[i].pre==0){p[i].pg=p[i].pa=1000;continue;}
   if(p[i].all)
    p[i].pa=(double)p[i].all/(double)p[i].pre;
   else p[i].pg=0;
   if(p[i].gold)
    p[i].pg=(double)p[i].gold/(double)p[i].pre;
   else p[i].pg=0;
  }
  sort(p,p+n,cmp1);
  ll rank=0,ranktemp=0;
  for(i=0;i<n;i++)
   if(i!=0 && p[i].gold==p[i-1].gold)
    p[i].r1=rank,ranktemp++;
   else
   {
    rank+=ranktemp+1;
    ranktemp=0;
    p[i].r1=rank;
   }
   
   sort(p,p+n,cmp2);
   rank=0,ranktemp=0;
   for(i=0;i<n;i++)
    if(i!=0 && p[i].all==p[i-1].all)
     p[i].r2=rank,ranktemp++;
    else
    {
     rank+=ranktemp+1;
     ranktemp=0;
     p[i].r2=rank;
    }
    sort(p,p+n,cmp5);
    rank=0,ranktemp=0;
    for(i=0;i<n;i++)
     if(i!=0 && p[i].pg==p[i-1].pg)
      p[i].r4=rank,ranktemp++;
     else
     {
      rank+=ranktemp+1;
      ranktemp=0;
      p[i].r4=rank;
     }
     sort(p,p+n,cmp3);
     rank=0,ranktemp=0;
     for(i=0;i<n;i++)
      if(i!=0 && p[i].pa==p[i-1].pa)
       p[i].r3=rank,ranktemp++;
      else
      {
       rank+=ranktemp+1;
       ranktemp=0;
       p[i].r3=rank;
      }
      sort(p,p+n,cmp4);
      
      while(m--){
       scanf("%d",&i);
       ll a=N,b;
       if(p[i].r1<a){a=p[i].r1;b=1;}
       if(p[i].r2<a){a=p[i].r2;b=2;}
       if(p[i].r4<a){a=p[i].r4;b=3;}
       if(p[i].r3<a){a=p[i].r3;b=4;}
       printf("%d:%d",a,b);
       if(m)printf(" ");
       else printf("\n");
      }
 }
 return 0;
}
/*
4 4
51 100 1000
36 110 300
6 14 32
5 18 40
0 1 2 3

7 2
51 100 1000
36 110 300
6 14 32
5 18 40
23 73 142
19 47 61
16 41 82
4 6
6 6
15 45 50
45 90 500
50 100 1000
30 80 75
50 100 500
40 90 100
2 4 1 5 3 0
4 4
2 3 1
1 3 1
2 5 1
0 4 1
1 3 2 0
*/