1055. The World's Richest (25)

题目地址：
http://www.patest.cn/contests/pat-a-practise/1055

这题需要剪枝（需要仔细读题目），网上参考了之后写的ac代码如下

/* 1055. The World's Richest (25) http://www.patest.cn/contests/pat-a-practise/1055 先进行Person结构体排序；由于题目中M的值小于等于100， 所以某个年龄出现的次数大于一百的时候可以过滤掉。 如果不这样做，Case 2会超时。 */
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
#include <vector>
#include <string>

using namespace std;

#define N 100002

struct person{
    char name[9];
    int age;
    int worth;
};

bool cmp(person p1, person p2)
{
    if (p1.worth > p2.worth)
        return true;
    if (p1.worth == p2.worth)
    {
        if (p1.age < p2.age)
            return true;
        if (p1.age == p2.age)
        {
            if (strcmp(p1.name,p2.name) < 0)
                return true;
        }
    }
    return false;
}

person num[N];

int main()
{
    //freopen("in", "r", stdin); 
    int n, k;
    scanf("%d%d", &n, &k);
    person pt;
    for (int i = 0; i < n; ++i){
        scanf("%s%d%d", num[i].name, &num[i].age, &num[i].worth);
    }
    sort(num, num + n,cmp); // 对所有的直接排序先

    int ageCount[201] = { 0 };

    int filter[N]; 

    int filter_num = 0;
    for (int i = 0; i < n; i++)
    {
        if (ageCount[num[i].age] < 100) // ageCount[] 存相应年龄的人数 M (<= 100)
        {
            ageCount[num[i].age]++;
            filter[filter_num++] = i;
        }
    }
    for (int i = 1; i <= k; i++){
        int m, amin, amax;
        scanf("%d%d%d", &m, &amin, &amax);
        printf("Case #%d:\n", i);
        int index = 0;
        for (int j = 0; j < filter_num; j++)
        {
            int k = filter[j];
            if (num[k].age >= amin && num[k].age <= amax && index < m)
            {
                printf("%s %d %d\n", num[k].name, num[k].age, num[k].worth);
                index++;
            }
        }
        if (index == 0)
            printf("None\n");
    }
    return 0;
}

ac2

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <list>
#include <stack> 
#include <map> 
#include <set> 
#include <iterator> 

using namespace std;

const int INF = 0x7fffffff; // 2 147 483 647
const int MIN_INF = - INF - 1; // -2 147 483 648

const int N = 100005;

struct per{
    string name;
    int age;
    int worth;
};

vector<per> peos;

int n, m;

bool cmp(per p1, per p2)
{
    if(p1.worth > p2.worth)
        return true;
    if(p1.worth == p2.worth)
    {
         if (p1.age < p2.age)
            return true;
        if (p1.age == p2.age)
        {
            return p1.name < p2.name;
        }
    }
    return false;
}

int main()
{
    //freopen("in.txt", "r", stdin);

    while(scanf("%d%d", &n , &m)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            per ptmp;
            cin >>  ptmp.name >> ptmp.age >> ptmp.worth;
            peos.push_back(ptmp);
        }

        sort(peos.begin(), peos.end(),cmp);

        vector<per> filter;
        vector<int> ageCnt(201, 0);
        // 每个年龄只取前面的100个人
        for(int i=0;i<n;i++)
        {
            int curAge = peos[i].age;
            if(ageCnt[curAge] < 100){
                filter.push_back(peos[i]);
                ageCnt[curAge] ++;
            }else{
                continue;
            }
        }

        int len = filter.size();

        for(int i=1;i<=m;i++)
        {
            int k;
            int ageMin,ageMax;
            scanf("%d%d%d", &k ,&ageMin, &ageMax);

             printf("Case #%d:\n", i);
            int index = 0;
            for (int j = 0; j < len; j++)
            {
                int ageTmp = filter[j].age;
                if (ageTmp >= ageMin && ageTmp <= ageMax && index < k)
                {
                    cout << filter[j].name << " " << filter[j].age << " " << filter[j].worth << endl;
                    index++;
                }
            }
            if (index == 0)
                printf("None\n");
            }
    }
    return 0;
}