PAT – 第27页

1098. Insertion or Heap Sort (25)-PAT甲级真题（堆排序）

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
Sample Output 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0
Sample Input 2:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9
Sample Output 2:
Heap Sort
5 4 3 1 0 2 6 7 8 9

题目大意：给出n和n个数的序列a和b，a为原始序列，b为排序其中的一个步骤，问b是a经过了堆排序还是插入排序的，并且输出它的下一步～

分析：插入排序的特点是：b数组前面的顺序是从小到大的，后面的顺序不一定，但是一定和原序列的后面的顺序相同～所以只要遍历一下前面几位，遇到不是从小到大的时候，开始看b和a是不是对应位置的值相等，相等就说明是插入排序，否则就是堆排序啦～

插入排序的下一步就是把第一个不符合从小到大的顺序的那个元素插入到前面已排序的里面的合适的位置，那么只要对前几个已排序的+后面一位这个序列sort排序即可～while(p <= n && b[p – 1] <= b[p]) p++；int index = p；找到第一个不满足条件的下标p并且赋值给index，b数组下标从1开始，所以插入排序的下一步就是sort(b.begin() + 1, b.begin() + index + 1)后的b数组～

堆排序的特点是后面是从小到大的，前面的顺序不一定，又因为是从小到大排列，堆排序之前堆为大顶堆，前面未排序的序列的最大值为b[1]，那么就可以从n开始往前找，找第一个小于等于b[1]的数字b[p]（while(p > 2 && b[p] >= b[1]) p–；），把它和第一个数字交换（swap(b[1], b[p])；），然后把数组b在1~p-1区间进行一次向下调整（downAdjust(b, 1, p – 1)；）～向下调整，low和high是需要调整的区间，因为是大顶堆，就是不断比较当前结点和自己的孩子结点哪个大，如果孩子大就把孩子结点和自己交换，然后再不断调整直到到达区间的最大值不能再继续了为止～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void downAdjust(vector<int> &b, int low, int high) {
    int i = 1, j = i * 2;
    while(j <= high) {
        if(j + 1 <= high && b[j] < b[j + 1]) j = j + 1;
        if (b[i] >= b[j]) break;
        swap(b[i], b[j]);
        i = j; j = i * 2;
    }
}
int main() {
    int n, p = 2;
    scanf("%d", &n);
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    while(p <= n && b[p - 1] <= b[p]) p++;
    int index = p;
    while(p <= n && a[p] == b[p]) p++;
    if(p == n + 1) {
        printf("Insertion Sort\n");
        sort(b.begin() + 1, b.begin() + index + 1);
    } else {
        printf("Heap Sort\n");
        p = n;
        while(p > 2 && b[p] >= b[1]) p--;
        swap(b[1], b[p]);
        downAdjust(b, 1, p - 1);
    }
    printf("%d", b[1]);
    for(int i = 2; i <= n; i++)
        printf(" %d", b[i]);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

void downAdjust(vector<int> &b, int low, int high) {

int i = 1, j = i * 2;

while(j <= high) {

if(j + 1 <= high && b[j] < b[j + 1]) j = j + 1;

if (b[i] >= b[j]) break;

swap(b[i], b[j]);

i = j; j = i * 2;

}

int main() {

int n, p = 2;

scanf("%d", &n);

vector<int> a(n + 1), b(n + 1);

for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

for(int i = 1; i <= n; i++) scanf("%d", &b[i]);

while(p <= n && b[p - 1] <= b[p]) p++;

int index = p;

while(p <= n && a[p] == b[p]) p++;

if(p == n + 1) {

printf("Insertion Sort\n");

sort(b.begin() + 1, b.begin() + index + 1);

} else {

printf("Heap Sort\n");

p = n;

while(p > 2 && b[p] >= b[1]) p--;

swap(b[1], b[p]);

downAdjust(b, 1, p - 1);

}

printf("%d", b[1]);

for(int i = 2; i <= n; i++)

printf(" %d", b[i]);

return 0;

}

1057. Stack (30)-PAT甲级真题（树状数组）

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian — return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 105). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian
where key is a positive integer no more than 105.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print “Invalid” instead.

Sample Input:
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
Sample Output:
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

题目大意：现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。
分析：用排序查询的方法会超时～～用树状数组，即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快～

#include <iostream>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

#include <iostream>

#include <stack>

#define lowbit(i) ((i) & (-i))

const int maxn = 100010;

using namespace std;

int c[maxn];

stack<int> s;

void update(int x, int v) {

for(int i = x; i < maxn; i += lowbit(i))

c[i] += v;

}

int getsum(int x) {

int sum = 0;

for(int i = x; i >= 1; i -= lowbit(i))

sum += c[i];

return sum;

}

void PeekMedian() {

int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;

while(left < right) {

mid = (left + right) / 2;

if(getsum(mid) >= k)

right = mid;

else

left = mid + 1;

}

printf("%d\n", left);

}

int main() {

int n, temp;

scanf("%d", &n);

char str[15];

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

scanf("%s", str);

if(str[1] == 'u') {

scanf("%d", &temp);

s.push(temp);

update(temp, 1);

} else if(str[1] == 'o') {

if(!s.empty()) {

update(s.top(), -1);

printf("%d\n", s.top());

s.pop();

} else {

printf("Invalid\n");

}

} else {

if(!s.empty())

PeekMedian();

else

printf("Invalid\n");

}

return 0;

}

L3-002. 堆栈-PAT团体程序设计天梯赛GPLT（树状数组）

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。

输入格式：

输入第一行给出正整数N（<= 105）。随后N行，每行给出一个操作指令，为下列3种指令之一：

Push key
Pop
PeekMedian
其中Push表示入栈，key是不超过105的正整数；Pop表示出栈；PeekMedian表示查中值。

输出格式：

对每个入栈指令，将key入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“Invalid”。

输入样例：
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
输出样例：
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

分析：如果排序查找的话会超时，用树状数组，即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快～

#include <cstdio>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

#include <cstdio>

#include <stack>

#define lowbit(i) ((i) & (-i))

const int maxn = 100010;

using namespace std;

int c[maxn];

stack<int> s;

void update(int x, int v) {

for(int i = x; i < maxn; i += lowbit(i))

c[i] += v;

}

int getsum(int x) {

int sum = 0;

for(int i = x; i >= 1; i -= lowbit(i))

sum += c[i];

return sum;

}

void PeekMedian() {

int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;

while(left < right) {

mid = (left + right) / 2;

if(getsum(mid) >= k)

right = mid;

else

left = mid + 1;

}

printf("%d\n", left);

}

int main() {

int n, temp;

scanf("%d", &n);

char str[15];

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

scanf("%s", str);

if(str[1] == 'u') {

scanf("%d", &temp);

s.push(temp);

update(temp, 1);

} else if(str[1] == 'o') {

if(!s.empty()) {

update(s.top(), -1);

printf("%d\n", s.top());

s.pop();

} else {

printf("Invalid\n");

}

} else {

if(!s.empty())

PeekMedian();

else

printf("Invalid\n");

}

return 0;

}

1075. PAT Judge (25)-PAT甲级真题

The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 positive integers, N (<=104), the total number of users, K (<=5), the total number of problems, and M (<=105), the total number of submittions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submittion in the following format:

user_id problem_id partial_score_obtained

where partial_score_obtained is either -1 if the submittion cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.

Output Specification:

For each test case, you are supposed to output the ranklist in the following format:

rank user_id total_score s[1] … s[K]

where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-” must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.

The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.

Sample Input:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0
Sample Output:
1 00002 63 20 25 – 18
2 00005 42 20 0 22 –
2 00007 42 – 25 – 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 –

分析：结构体数组中passnum统计完整通过的题目个数，isshown在用户有一题通过了编译器（不管得不得0分）的时候置为true。vector<int> score;记录每门课的最高分
因为没有通过编译器的分数为0，但是没有提交过的分数为“-”，所以把有一门课每次都是未通过编译器的那门课分数置为-2。初始化数组分数为-1，所以可以根据-1和-2判断当前分数是提交过了没通过编译器的，还是没提交过的题目
注意：因为最后一个测试样例是有一个人一开始得到了分数，后来提交了一次没有通过编译器的，所以要判断在分数每次更新最大值之后if(v[id].score[num] == -1)，说明最好成绩只是-1（也就是没通过编译器或者没有提交过），这个时候再置v[id].score[num] = -2，否则会误操作把已经提交过很好分数的人的成绩抹掉成了-2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int rank, id, total = 0;
    vector<int> score;
    int passnum = 0;
    bool isshown = false;
};
bool cmp1(node a, node b) {
    if(a.total != b.total)
        return a.total > b.total;
    else if(a.passnum != b.passnum)
        return a.passnum > b.passnum;
    else
        return a.id < b.id;
}

int main() {
    int n, k, m, id, num, score;
    scanf("%d %d %d", &n, &k, &m);
    vector<node> v(n + 1);
    for(int i = 1; i <= n; i++)
        v[i].score.resize(k + 1, -1);
    vector<int> full(k + 1);
    for(int i = 1; i <= k; i++)
        scanf("%d", &full[i]);
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &id, &num, &score);
        v[id].id = id;
        v[id].score[num] = max(v[id].score[num], score);
        if(score != -1)
            v[id].isshown = true;
        else if(v[id].score[num] == -1)
            v[id].score[num] = -2;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            if(v[i].score[j] != -1 && v[i].score[j] != -2)
                v[i].total += v[i].score[j];
            if(v[i].score[j] == full[j])
                v[i].passnum++;
        }
    }
    sort(v.begin() + 1, v.end(), cmp1);
    for(int i = 1; i <= n; i++) {
        v[i].rank = i;
        if(i != 1 && v[i].total == v[i - 1].total)
            v[i].rank = v[i - 1].rank;
    }
    for(int i = 1; i <= n; i++) {
        if(v[i].isshown == true) {
            printf("%d %05d %d", v[i].rank, v[i].id, v[i].total);
            for(int j = 1; j <= k; j++) {
                if(v[i].score[j] != -1 && v[i].score[j] != -2)
                    printf(" %d", v[i].score[j]);
                else if(v[i].score[j] == -1)
                    printf(" -");
                else
                    printf(" 0");
            }
            printf("\n");
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int rank, id, total = 0;

vector<int> score;

int passnum = 0;

bool isshown = false;

};

bool cmp1(node a, node b) {

if(a.total != b.total)

return a.total > b.total;

else if(a.passnum != b.passnum)

return a.passnum > b.passnum;

else

return a.id < b.id;

}

int main() {

int n, k, m, id, num, score;

scanf("%d %d %d", &n, &k, &m);

vector<node> v(n + 1);

for(int i = 1; i <= n; i++)

v[i].score.resize(k + 1, -1);

vector<int> full(k + 1);

for(int i = 1; i <= k; i++)

scanf("%d", &full[i]);

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

scanf("%d %d %d", &id, &num, &score);

v[id].id = id;

v[id].score[num] = max(v[id].score[num], score);

if(score != -1)

v[id].isshown = true;

else if(v[id].score[num] == -1)

v[id].score[num] = -2;

}

for(int i = 1; i <= n; i++) {

for(int j = 1; j <= k; j++) {

if(v[i].score[j] != -1 && v[i].score[j] != -2)

v[i].total += v[i].score[j];

if(v[i].score[j] == full[j])

v[i].passnum++;

}

sort(v.begin() + 1, v.end(), cmp1);

for(int i = 1; i <= n; i++) {

v[i].rank = i;

if(i != 1 && v[i].total == v[i - 1].total)

v[i].rank = v[i - 1].rank;

}

for(int i = 1; i <= n; i++) {

if(v[i].isshown == true) {

printf("%d %05d %d", v[i].rank, v[i].id, v[i].total);

for(int j = 1; j <= k; j++) {

if(v[i].score[j] != -1 && v[i].score[j] != -2)

printf(" %d", v[i].score[j]);

else if(v[i].score[j] == -1)

printf(" -");

else

printf(" 0");

}

printf("\n");

}

return 0;

}

1071. Speech Patterns (25)-PAT甲级真题（map应用）

People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.

Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?

Input Specification:

Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return ‘\n’. The input contains at least one alphanumerical character, i.e., one character from the set [0-9 A-Z a-z].

Output Specification:

For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

Note that words are case insensitive.

Sample Input:
Can1: “Can a can can a can? It can!”
Sample Output:
can 5

题目大意：统计单词个数～大小写字母+数字的组合才是合法的单词，给出一个字符串，求出现的合法的单词的个数最多的那个单词，以及它出现的次数。如果有并列的，那么输出字典序里面的第一个～～
分析：用map很简单的~不过呢~有几个注意点～：
1. 大小写不区分，所以统计之前要先s[i] = tolower(s[i]);
2. [0-9 A-Z a-z]可以简写为cctype头文件里面的一个函数isalnum～～
3. 必须用getline读入一长串的带空格的字符串～～
4. 一定要当t不为空的时候m[t]++，因为t为空也会被统计的！！！～～
5. 最重要的是～如果i已经到了最后一位，不管当前位是不是字母数字，都得将当前这个t放到map里面（只要t长度不为0）～

#include <iostream>
#include <map>
#include <cctype>
using namespace std;
int main() {
    string s, t;
    getline(cin, s);
    map<string, int> m;
    for(int i = 0; i < s.length(); i++) {
        if(isalnum(s[i])) {
            s[i] = tolower(s[i]);
            t += s[i];
        }
        if(!isalnum(s[i]) || i == s.length() - 1){
            if(t.length() != 0) m[t]++;
            t = "";
        }
    }
    int maxn = 0;
    for(auto it = m.begin(); it != m.end(); it++) {
        if(it->second > maxn) {
            t = it->first;
            maxn = it->second;
        }
    }
    cout << t << " " << maxn;
    return 0;
}

#include <iostream>

#include <map>

#include <cctype>

using namespace std;

int main() {

string s, t;

getline(cin, s);

map<string, int> m;

for(int i = 0; i < s.length(); i++) {

if(isalnum(s[i])) {

s[i] = tolower(s[i]);

t += s[i];

}

if(!isalnum(s[i]) || i == s.length() - 1){

if(t.length() != 0) m[t]++;

t = "";

}

int maxn = 0;

for(auto it = m.begin(); it != m.end(); it++) {

if(it->second > maxn) {

t = it->first;

maxn = it->second;

}

cout << t << " " << maxn;

return 0;

}

1055. The World’s Richest (25)-PAT甲级真题

Forbes magazine publishes every year its list of billionaires based on the annual ranking of the world’s wealthiest people. Now you are supposed to simulate this job, but concentrate only on the people in a certain range of ages. That is, given the net worths of N people, you must find the M richest people in a given range of their ages.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=105) – the total number of people, and K (<=103) – the number of queries. Then N lines follow, each contains the name (string of no more than 8 characters without space), age (integer in (0, 200]), and the net worth (integer in [-106, 106]) of a person. Finally there are K lines of queries, each contains three positive integers: M (<= 100) – the maximum number of outputs, and [Amin, Amax] which are the range of ages. All the numbers in a line are separated by a space.

Output Specification:

For each query, first print in a line Case #X: where X is the query number starting from 1. Then output the M richest people with their ages in the range [Amin, Amax]. Each person’s information occupies a line, in the format

Name Age Net_Worth
The outputs must be in non-increasing order of the net worths. In case there are equal worths, it must be in non-decreasing order of the ages. If both worths and ages are the same, then the output must be in non-decreasing alphabetical order of the names. It is guaranteed that there is no two persons share all the same of the three pieces of information. In case no one is found, output “None”.
Sample Input:
12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50
Sample Output:
Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None

题目大意：给出n个人的姓名、年龄和拥有的钱，然后进行k次查询，每次查询输出在年龄区间内的财富值的从大到小的前m个人的信息。如果财富值相同就就先输出年龄小的，如果年龄相同就把名字按照字典序排序输出～
分析：不能先排序然后根据每一个条件再新建一个数组、对新数组排序的方法，这样测试点2会超时～因为n和m的悬殊太大了，n有10的5次方，m却只有100个。所以先把所有的人按照财富值排序，再建立一个数组book标记每个年龄段拥有的人的数量，遍历数组并统计相应年龄的人数，当当前年龄的人的数量不超过100的时候压入新的数组，多出来的不要压入新数组中（也就是说只取每个年龄的前100名，因为一个年龄段最小的就是一个年龄，即使这样也不会超过100个需要输出），再从这个新的数组里面取符合相应年龄的人的信息～～

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
struct node {
    char name[10];
    int age, money;
};
int cmp1(node a, node b) {
    if(a.money != b.money)
        return a.money > b.money;
    else if(a.age != b.age)
        return a.age < b.age;
    else
        return (strcmp(a.name, b.name) < 0);
}
int main() {
    int n, k, num, amin, amax;
    scanf("%d %d", &n, &k);
    vector<node> vt(n), v;
    vector<int> book(205, 0);
    for(int i = 0; i < n; i++)
        scanf("%s %d %d", vt[i].name, &vt[i].age, &vt[i].money);
    sort(vt.begin(), vt.end(), cmp1);
    for(int i = 0; i < n; i++) {
        if(book[vt[i].age] < 100) {
            v.push_back(vt[i]);
            book[vt[i].age]++;
        }
    }
    for(int i = 0; i < k; i++) {
        scanf("%d %d %d", &num, &amin, &amax);
        vector<node> t;
        for(int j = 0; j < v.size(); j++) {
            if(v[j].age >= amin && v[j].age <= amax)
                t.push_back(v[j]);
        }
        if(i != 0) printf("\n");
        printf("Case #%d:", i + 1);
        int flag = 0;
        for(int j = 0; j < num && j < t.size(); j++) {
            printf("\n%s %d %d", t[j].name, t[j].age, t[j].money);
            flag = 1;
        }
        if(flag == 0) printf("\nNone");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

struct node {

char name[10];

int age, money;

};

int cmp1(node a, node b) {

if(a.money != b.money)

return a.money > b.money;

else if(a.age != b.age)

return a.age < b.age;

else

return (strcmp(a.name, b.name) < 0);

}

int main() {

int n, k, num, amin, amax;

scanf("%d %d", &n, &k);

vector<node> vt(n), v;

vector<int> book(205, 0);

for(int i = 0; i < n; i++)

scanf("%s %d %d", vt[i].name, &vt[i].age, &vt[i].money);

sort(vt.begin(), vt.end(), cmp1);

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

if(book[vt[i].age] < 100) {

v.push_back(vt[i]);

book[vt[i].age]++;

}

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

scanf("%d %d %d", &num, &amin, &amax);

vector<node> t;

for(int j = 0; j < v.size(); j++) {

if(v[j].age >= amin && v[j].age <= amax)

t.push_back(v[j]);

}

if(i != 0) printf("\n");

printf("Case #%d:", i + 1);

int flag = 0;

for(int j = 0; j < num && j < t.size(); j++) {

printf("\n%s %d %d", t[j].name, t[j].age, t[j].money);

flag = 1;

}

if(flag == 0) printf("\nNone");

}

return 0;

}