首页 > ACM题库 > HDU-杭电 > HDU 3789-奥运排序问题-排序-[解题报告]HOJ
2015
04-13

HDU 3789-奥运排序问题-排序-[解题报告]HOJ

奥运排序问题

问题描述 :

按要求,给国家进行排名。

输入:

有多组数据。
第一行给出国家数N,要求排名的国家数M,国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数,奖牌数,人口数(百万)。
接下来一行给出M个国家号。

输出:

有多组数据。
第一行给出国家数N,要求排名的国家数M,国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数,奖牌数,人口数(百万)。
接下来一行给出M个国家号。

样例输入:

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

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3789

首先 题目要求只对m个国家排序,然后输出的顺序是给的国家编号的顺序~~!!  不一定是升序` wa了n次在这里

然后用sort死做

代码:

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;

struct   nation
{
    long double  gold;
    long double  all;
    long double  area;
    int id;
    int rate1;
    int rate2;
    int rate3;
    int rate4;
    int bestrate;
    int sortway;

};


int cmpway;

bool cmp(nation a,nation b)
{
   if(cmpway==0)   return a.id<b.id;
   else  if(cmpway==1)return a.gold>b.gold;

   else if(cmpway==2)  return a.all>b.all;

   else if(cmpway==3)  return a.gold/a.area>b.gold/b.area;

   else if(cmpway==4)  return a.all/a.area>b.all/b.area;

 }

int main()
{
  int n,m;
  bool flag=0;
  while(cin>>n>>m)
  {


        nation p[n];

        vector<nation>  vn;

      double gold,all,area;
      for(int i=0;i<n;i++)
       {
          scanf("%lf%lf%lf",&gold,&all,&area);
          p[i].gold=gold;
          p[i].all=all;
          p[i].area=area;
          p[i].id=i;
       }

         int   temp;
        for(int i=0;i<m;i++)
         {
              scanf("%d",&temp);
              vn.push_back(p[temp]);
              vn[i].id=i;

         }
        if(m>0)
        {

      cmpway=1;
      sort(vn.begin(),vn.end(),cmp);
      for(int i=0;i<m;i++)
       {
          vn[i].rate1=i;
       }

       for(int i=1;i<m;i++)
       {
          if(vn[i].gold==vn[i-1].gold)   vn[i].rate1=vn[i-1].rate1;

       }


      cmpway=2;
      sort(vn.begin(),vn.end(),cmp);
      for(int i=0;i<m;i++)
       {
          vn[i].rate2=i;
       }

       for(int i=1;i<m;i++)
       {
          if(vn[i].all==vn[i-1].all)   vn[i].rate2=vn[i-1].rate2;

       }

      cmpway=3;
      sort(vn.begin(),vn.end(),cmp);
      for(int i=0;i<m;i++)
       {
          vn[i].rate3=i;
       }

       for(int i=1;i<m;i++)
       {
          if(vn[i].gold/vn[i].area==vn[i-1].gold/vn[i-1].area)   vn[i].rate3=vn[i-1].rate3;

       }

       cmpway=4;
      sort(vn.begin(),vn.end(),cmp);
      for(int i=0;i<m;i++)
       {
          vn[i].rate4=i;
       }

       for(int i=1;i<m;i++)
       {
          if(vn[i].all/vn[i].area==vn[i-1].all/vn[i-1].area)   vn[i].rate4=vn[i-1].rate4;

       }


       cmpway=0;
       sort(vn.begin(),vn.end(),cmp);


      for(int i=0;i<m;i++)
        {

           vn[i].bestrate=vn[i].rate1;
           vn[i].sortway=1;
           if(vn[i].rate2<vn[i].bestrate)
           {
              vn[i].bestrate=vn[i].rate2;
              vn[i].sortway=2;
           }

           if(vn[i].rate3<vn[i].bestrate)
           {
              vn[i].bestrate=vn[i].rate3;
              vn[i].sortway=3;
           }

           if(vn[i].rate4<vn[i].bestrate)
           {
              vn[i].bestrate=vn[i].rate4;
              vn[i].sortway=4;
           }

        }
//        if(flag==1)  printf("\n");
//        if(flag==0)  flag=1;
         for(int i=0;i<m;i++)
            printf("%d:%d\n",vn[i].bestrate+1,vn[i].sortway);
        }
        cout<<endl;
  }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/jingqi814/article/details/11771959


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept