首页 > 代码库 > PAT-1055. The World's Richest (25)
PAT-1055. The World's Richest (25)
这道题目就是一个排序题目，但是如果简单的排序会超时，需要剪掉一部分数据。
最多输出100名数据，排序后，那么相同年龄的后面的数据就不会输出了，所以也不需记录在查找序列里面。因此这部分数据可以忽略掉。
bool cmp return true means right position.
make_heap(iterato_begin,iterator_end);
heap_sort(iterator_begin,iterator_end); 堆排序。
// 1055.cpp : 定义控制台应用程序的入口点。//// 1055.cpp : 定义控制台应用程序的入口点。#include"stdafx.h"#include<string.h>#include<string>#include<vector>#include<iostream>#include<algorithm>using namespace std;struct Item{ Item(string name,int age,int worth) { this->name=name; this->age=age; this->worth=worth; } bool operator<(const Item & it) const { if(this->worth>it.worth) return true; else if(this->worth==it.worth) { if(this->age<it.age) return true; else if(this->age==it.age) { if(this->name<it.name) return true; } } return false; } string name; int age; int worth;};vector<Item> v;int agecount[210];int member[100010];int main(){ int n,k; char name[10]; int value,worth; freopen("1055.txt","r",stdin); while(scanf("%d%d",&n,&k)!=EOF) { memset(agecount,0,210); for(int i=0;i<n;i++) { scanf("%s %d %d",name,&value,&worth); v.push_back(Item(string(name),value,worth)); } int ind=0; for(int i=0;i<n;i++) { int age=v[i].age; if(agecount[age]++<=100) { member[ind++]=i; } } //make_heap(v.begin(),v.end()); //sort_heap(v.begin(),v.end()); sort(v.begin(),v.end()); int num,b,e; for(int i=1;i<=k;i++) { printf("Case #%d:\n",i); scanf("%d%d%d",&num,&b,&e); bool flag=false; for(int j=0;j<ind;j++) { int tmp=member[j]; Item item=v[tmp]; if(item.age>=b&&item.age<=e) { flag=true; printf("%s %d %d\n",item.name.c_str(),item.age,item.worth); num--; if(num<=0) break; } } if(!flag) printf("None\n"); } } return 0;}
PAT-1055. The World's Richest (25)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。