PAT 甲级 - 算法初步

接上一篇 PAT 甲级 - 入门模拟 ，自我感觉这部分才是真正的算法入门，对基础的数据结构提供了很好的类型题进行匹配练习

包括分类：排序 、 散列 、 贪心 、 二分 、 双指针 、 打表、递推

排序

思想解释

排序题主要是获取排序后的结果而不是过程，大部分代码可以使用 sort() 函数进行直接处理，要熟练编写 cmp 排序规则（包括结构体形式的多变量规则）

有些题需要获取排名，只需在已经排序好的数组或容器中遍历全部的数据，如果和上一个数据相同，则排名相同，否则排名加 1

类型练习

1062

题目：Talent and Virtue

About 900 years ago, a Chinese philosopher Sima Guang wrote a history book in which he talked about people’s talent and virtue. According to his theory, a man being outstanding in both talent and virtue must be a “sage（圣人）”; being less excellent but with one’s virtue outweighs talent can be called a “nobleman（君子）”; being good in neither is a “fool man（愚人）”; yet a fool man is better than a “small man（小人）” who prefers talent than virtue.

Now given the grades of talent and virtue of a group of people, you are supposed to rank them according to Sima Guang’s theory.

Input Specification:

Each input file contains one test case. Each case first gives 3 positive integers in a line: $N (≤105)$, the total number of people to be ranked; $L (≥60)$, the lower bound of the qualified grades – that is, only the ones whose grades of talent and virtue are both not below this line will be ranked; and $H(<100)$, the higher line of qualification – that is, those with both grades not below this line are considered as the “sages”, and will be ranked in non-increasing order according to their total grades. Those with talent grades below H but virtue grades not are cosidered as the “noblemen”, and are also ranked in non-increasing order according to their total grades, but they are listed after the “sages”. Those with both grades below H, but with virtue not lower than talent are considered as the “fool men”. They are ranked in the same way but after the “noblemen”. The rest of people whose grades both pass the L line are ranked after the “fool men”.

Then N lines follow, each gives the information of a person in the format:

ID_Number Virtue_Grade Talent_Grade

where ID_Number is an 8-digit number, and both grades are integers in $[0, 100]$. All the numbers are separated by a space.

Output Specification:

The first line of output must give $M(≤N)$, the total number of people that are actually ranked. Then M lines follow, each gives the information of a person in the same format as the input, according to the ranking rules. If there is a tie of the total grade, they must be ranked with respect to their virtue grades in non-increasing order. If there is still a tie, then output in increasing order of their ID’s.

Sample Input:

14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60

Sample Output:

12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90

思路： 使用结构体对每个学生的信息进行存储，根据题意编写排序规则

• 存储学生信息的结构体除了基本信息外还应包含总成绩 (total) 与类别 (rank)

• 编写排序规则，升序用小于号 "<"，降序反之

• 使用动态容器 vector 创建一个结构体数组，处理时将及格的放入数组，最后输出 size

• 在循环中创建一个临时结构体变量进行数据的处理，符合哪种条件就将 rank 置于相应的等级

• 需要注意读题， not lower than就代表 >=

代码：

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

struct Student
{

    int Id, virtue, talent, total;
    int rank; // 表示类别，1~4

}; 

bool cmp(Student a, Student b)
{ // 排序规则

    if (a.rank != b.rank)
    { // 类别不同，按类别从小到大
        return a.rank < b.rank;
    }
    else if (a.total != b.total)
    {
        return a.total > b.total;
    }
    else if (a.virtue != b.virtue)
    {
        return a.virtue > b.virtue;
    }
    else
    { // 全部相同，按学号
        return a.Id < b.Id;
    }

}

int main()
{

    int n, low, height;
    cin >> n >> low >> height;
    vector<Student> stu; // 建立一个结构体的动态数组
    for (int i = 0; i < n; i++)
    {
        Student temp; // 临时结构体变量
        cin >> temp.Id >> temp.virtue >> temp.talent;
        temp.total = temp.virtue + temp.talent; // 对每一个数据都计算它的总成绩
        if (temp.virtue < low || temp.talent < low)
        {
            continue; // 如果不符合条件直接处理下一个
        }
        else if (temp.virtue >= height && temp.talent >= height) // 这里可以是等于
        {
            temp.rank = 1;
            stu.push_back(temp);
        }
        else if (temp.virtue >= height && temp.talent < height)
        {
            temp.rank = 2;
            stu.push_back(temp);
        }
        else if (temp.virtue < height && temp.talent < height && temp.virtue >= temp.talent) // 不小于
        {
            temp.rank = 3;
            stu.push_back(temp);
        }
        else
        {
            temp.rank = 4;
            stu.push_back(temp);
        }
    }
    sort(stu.begin(), stu.end(), cmp); // 根据规则排序
    cout << stu.size() << endl;        // 输出符合条件的人数
    for (int i = 0; i < stu.size(); i++)
    { // 按规则循环输出
        cout << stu[i].Id << " " << stu[i].virtue << " " << stu[i].talent << endl;
    }

    system("pause");
    return 0;

}

1012

题目：The Best Rank

To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C - C Programming Language, M - Mathematics (Calculus or Linear Algrbra), and E - English. At the mean time, we encourage students by emphasizing on their best ranks – that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.

For example, The grades of C, M, E and A - Average of 4 students are given as the following:

StudentID   C  M  E  A
 310101     98 85 88 90
 310102     70 95 88 84
 310103     82 87 94 88
 310104     91 91 91 91

Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (≤2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of C , M and E . Then there are M lines, each containing a student ID.

Output Specification:

For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.

The priorities of the ranking methods are ordered as A > C > M > E . Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.

If a student is not on the grading list, simply output N/A .

Sample Input:

5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999

Sample Output:

1 C
1 M
1 E
1 A
3 A
N/A

思路： 编写排序规则对每一科进行排序将排名放到结构体相应位置，使用 Map 集合创建索引，进行查询

• 使用结构体对每个学生进行存储，成绩和排名用数组的方式创建

• 循环输入，平均分要四舍五入，使用 answer+0.5的方式实现

• 对每一科进行排序，编写循环式排序规则时，下标变量必须提前定义，处理并列排名的情况

• 将最后一轮排序（数据全部处理完）后的顺序，以 ID 为键，下标为值的方式放入 Map 集合方便查询 (unordered_map 时间更短）

• 对每一个被查询学生查找排名最小的一项，返回其值并获得课程下标，按格式输出

代码：

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std; 

struct Student // 学生结构体
{

    string Id;
    int grades[4], ranks[4];           // 对应的成绩和排名

} stu[2000]; // 不会超过 2000 人
char course[5] = {'A', 'C', 'M', 'E'}; // 对应的课程，方便输出（这里的构造顺序要和处理时的顺序必须一致，顺序用题目给出的优先级即可）
int now, r; // 表示课程和排名的处理
bool cmp(Student a, Student b)
{

    return a.grades[now] > b.grades[now];

}

int main()
{

    int n, m;
    cin >> n >> m;
    unordered_map<string, int> Map; // 用于存储 ID 对应的下标，方便查询
    for (int i = 0; i < n; i++)
    {
        cin >> stu[i].Id >> stu[i].grades[1] >> stu[i].grades[2] >> stu[i].grades[3];
        stu[i].grades[0] = (stu[i].grades[1] + stu[i].grades[2] + stu[i].grades[3]) / 3 + 0.5; // 平均值四舍五入
    }

    for (now = 0; now < 4; now++) // 按每科成绩进行排序
    {
        sort(stu, stu + n, cmp);
        for (int i = 0; i < n; i++)
        {
            if (stu[i].grades[now] != stu[i - 1].grades[now] || i == 0)
            {
                r = i + 1; // 处理排名并列的情况
            }
            stu[i].ranks[now] = r;
        }
    }

    for (int i = 0; i < n; i++)
    {
        Map[stu[i].Id] = i; // 数据处理完成后将 ID 和下标对应存储，方便查询
    }

    while (m--)
    {
        string query;
        cin >> query;
        if (!Map.count(query)) // 没查询到元素
        {
            cout << "N/A\n";
        }
        else
        {
            int index = Map[query], minRank = 2001, cour; // 查询到了，获取其下标
            for (int i = 0; i < 4; i++)
            {
                if (stu[index].ranks[i] < minRank)
                {
                    minRank = stu[index].ranks[i]; // 寻找这个学生的最小排名
                    cour = i;                      // 获取最小排名的课程下标
                }
            }
            cout << minRank << " " << course[cour] << endl;
        }
    }

    system("pause");
    return 0;

}

1016

题目：Phone Bills

A long-distance telephone company charges its customers by the following rules:

Making a long-distance call costs a certain amount per minute, depending on the time of day when the call is made. When a customer starts connecting a long-distance call, the time will be recorded, and so will be the time when the customer hangs up the phone. Every calendar month, a bill is sent to the customer for each minute called (at a rate determined by the time of day). Your job is to prepare the bills for each month, given a set of phone call records.

Input Specification:

Each input file contains one test case. Each case has two parts: the rate structure, and the phone call records.
The rate structure consists of a line with 24 non-negative integers denoting the toll (cents/minute) from $00:00 - 01:00$, the toll from $01:00 - 02:00$, and so on for each hour in the day.
The next line contains a positive number $N (≤1000)$, followed by N lines of records. Each phone call record consists of the name of the customer (string of up to 20 characters without space), the time and date (MM:dd:HH:mm), and the word on-line or off-line.
For each test case, all dates will be within a single month. Each on-line record is paired with the chronologically next record for the same customer provided it is an off-line record. Any on-line records that are not paired with an off-line record are ignored, as are off-line records not paired with an on-line record. It is guaranteed that at least one call is well paired in the input. You may assume that no two records for the same customer have the same time. Times are recorded using a 24-hour clock.

Output Specification:

For each test case, you must print a phone bill for each customer.
Bills must be printed in alphabetical order of customers’ names. For each customer, first print in a line the name of the customer and the month of the bill in the format shown by the sample. Then for each time period of a call, print in one line the beginning and ending time and date (dd:HH:mm), the lasting time (in minute) and the charge of the call. The calls must be listed in chronological order. Finally, print the total charge for the month in the format shown by the sample.

Sample Input:

10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
10
CYLL 01:01:06:01 on-line
CYLL 01:28:16:05 off-line
CYJJ 01:01:07:00 off-line
CYLL 01:01:08:03 off-line
CYJJ 01:01:05:59 on-line
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:04:23:59 off-line

Sample Output:

CYJJ 01
01:05:59 01:07:00 61 $12.10
Total amount: $12.10
CYLL 01
01:06:01 01:08:03 122 $24.40
28:15:41 28:16:05 24 $3.85
Total amount: $28.25
aaa 01
02:00:01 04:23:59 4318 $638.80
Total amount: $638.80

思路： 使用 Map 集合对名字自动排序，集合值为通话记录结构体组成的动态数组

• 使用结构体存储通话记录，定义一个 time 用来记录开年零点到记录的时间（分钟为单位）方便后续比较和处理

• 使用 Map 集合存储姓名对应的结构体数组，Map 自动排序，处理时遍历取出即可

• 对取出的数组中对所有的通话记录进行排序，判断每两条记录的状态进行话费的计算

代码：

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

struct Record // 结构体记录每条通话记录的信息，名字是公共的所以无需放入
{
    string status;
    int month, day, hour, minute, time; //time 表示的是开年零点到现在的时间（分钟为单位）
};

bool cmp(Record a, Record b) // 定义一个时间的排序规则
{
    return a.time < b.time;
}

int main()
{
    double rate[24]; // 输入收费标准，时间也是从 0 开始，无需进行下标的增减
    for (int i = 0; i < 24; i++)
    {
        cin >> rate[i];
    }
    int n;
    cin >> n;
    getchar();                          // 后边输入字符串，截获换行符
    map<string, vector<Record>> custom; // 用名字作为键值，直接对其进行排序
    for (int i = 0; i < n; i++)
    {
        Record temp;
        string temp_name; // 作为键放入 Map，临时变量即可
        cin >> temp_name;
        //cin>> temp.month >> temp.day >> temp.hour >> temp.minute;
        // 这种输出对有 ":" 间隔的数据无法处理，可以加一个 char c 截获，或使用下面 scanf 的方式输入
        scanf("%d:%d:%d:%d", &temp.month, &temp.day, &temp.hour, &temp.minute);
        cin >> temp.status;
        temp.time = temp.day * 1440 + temp.hour * 60 + temp.minute; // 统一转换成分钟方便运算
        custom[temp_name].push_back(temp);                          // 以姓名为键，记录数组为值放入集合
    }
    for (auto it : custom)
    {
        auto temp_V = it.second;                 // 将每个人的通话记录数组拿出来，对每个数组进行处理
        sort(temp_V.begin(), temp_V.end(), cmp); // 对所有的通话记录进行排序
        double total_bill = 0;
        for (int i = 0; i < temp_V.size();) // 分组判断，不直接递增
        {
            if (i + 1 < temp_V.size() && temp_V[i].status > temp_V[i + 1].status) //on 按字典序高于 off，一组符合规则的数据
            {
                if (!total_bill) // 使用非的方式只输出一次姓名，后续 total 有值便为 0
                {
                    cout << it.first;
                    printf(" %02d\n", temp_V[i].month);
                }
                double per_bill = 0;
                int time1 = temp_V[i].time, time2 = temp_V[i + 1].time;
                for (int j = time1; j < time2; j++) // 模拟时间
                {
                    per_bill += rate[j % 1440 / 60]; // 每分钟的单价相加
                }
                printf("%02d:%02d:%02d ", temp_V[i].day, temp_V[i].hour, temp_V[i].minute);
                printf("%02d:%02d:%02d ", temp_V[i + 1].day, temp_V[i + 1].hour, temp_V[i + 1].minute);
                printf("%d $%.2f\n", temp_V[i + 1].time - temp_V[i].time, per_bill / 100);
                total_bill += per_bill;
                i += 2; // 一组成功下一组
            }
            else
            {
                i++; // 一组不成功，以结束时间作为下一组的开始时间
            }
        }
        if (total_bill) // 这个是在人物之外，还需判断一次，防止有人存在的账单都不符合条件但还是输出了 total_bill
        {
            printf("Total amount: $%.2f\n", total_bill / 100); // 账单以时间为单位
        }
    }
    system("pause");
    return 0;
}

1025

题目：PAT Ranking

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number $N (≤100)$, the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer $K (≤300)$, the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank

The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

Sample Output:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

思路： 结构体 + 动态数组存储，分情况处理排名，考场内排名的处理用临时数组每输入完一个考场处理一次的形式

代码：

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

struct Student
{

    string num;
    int score, ranks[2], room; //ranks[0] 代表总排名，1 代表考场排名

}; 
bool cmp(Student a, Student b) // 排序规则
{

    return a.score == b.score ? a.num < b.num : a.score > b.score;

}
int r; // 处理并列排名

int main()
{

    int n, m;
    cin >> n;
    vector<Student> stu; // 所有成员的结构体动态数组
    for (int i = 0; i < n; i++)
    {
        cin >> m;
        getchar(); // 捕捉换行符
        Student temp_stu[m];
        for (int j = 0; j < m; j++)
        {
            cin >> temp_stu[j].num >> temp_stu[j].score;
            temp_stu[j].room = i + 1; // 考场号就等于组数 +1
        }
        sort(temp_stu, temp_stu + m, cmp); // 对一个考场的所有成员进行排序
        for (int k = 0; k < m; k++)
        {
            if (k == 0 || temp_stu[k].score != temp_stu[k - 1].score)
            {
                r = k + 1;
            }
            temp_stu[k].ranks[1] = r;   // 赋值考场排名
            stu.push_back(temp_stu[k]); // 放入总数组
        }
    }
    sort(stu.begin(), stu.end(), cmp); // 公共排名处理
    for (int i = 0; i < stu.size(); i++)
    {
        if (i == 0 || stu[i].score != stu[i - 1].score)
        {
            r = i + 1;
        }
        stu[i].ranks[0] = r;
    }
    cout << stu.size() << endl;
    for (int i = 0; i < stu.size(); i++)
    {
        cout << stu[i].num << " " << stu[i].ranks[0] << " " << stu[i].room << " " << stu[i].ranks[1] << endl;
    }

    system("pause");
    return 0;

}

1028

题目：List Sorting

Excel can sort records according to any column. Now you are supposed to imitate this function.

Input Specification:

Each input file contains one test case. For each case, the first line contains two integers $N (≤10^5)$ and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).

Output Specification:

For each test case, output the sorting result in N lines. That is, if $C = 1$ then the records must be sorted in increasing order according to ID’s; if $C = 2$ then the records must be sorted in non-decreasing order according to names; and if $C = 3$ then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.

Sample Input 1:

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

Sample Output 1:

000001 Zoe 60
000007 James 85
000010 Amy 90

思路： 设置变量 C 在排序规则之外，根据 C 的值返回相应的规则；注意 non-decreasing 表示非降序（≠升序）比较运算符要用 <=

代码：

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

struct Student
{
    string Id, name;
    int score;
};
int c;
bool cmp(Student a, Student b)
{
    if (c == 1)
    {
        return a.Id < b.Id;
    }
    else if (c == 2)
    {
        return a.name == b.name ? a.Id < b.Id : a.name <= b.name;
    }
    else if (c == 3)
    {
        return a.score == b.score ? a.Id < b.Id : a.score <= b.score;
    }
    return 0;
}

int main()
{
    int n;
    vector<Student> stu;
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++)
    {
        Student temp;
        cin >> temp.Id >> temp.name >> temp.score;
        stu.push_back(temp);
    }
    sort(stu.begin(), stu.end(), cmp);
    for (int i = 0; i < stu.size(); i++)
    {
        printf("%s %s %d\n", stu[i].Id.c_str(), stu[i].name.c_str(), stu[i].score);
    }
    system("pause");
    return 0;
}

1055

题目：The World’s Richest

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 (≤10^5)$ - the total number of people, and $K (≤10^3)$ - 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

思路： 使用多个结构体动态数组，挑选数据后只排序一次，减少复杂度

• 结构体的字符串使用字符数组，配合 scanf() 减少复杂度

• 输入数据后按规则进行排序，如果年龄相同只保存 100 人，减少遍历长度

代码：

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

struct Person
{

    char name[10]; // 使用字符数组，配合 scanf() 减少复杂度
    int age, money;

}; 

bool cmp(Person a, Person 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;
    scanf("%d %d", &n, &k);
    vector<Person> temp_in(n); // 输入数组
    for (int i = 0; i < n; i++)
    {
        scanf("%s %d %d", &temp_in[i].name, &temp_in[i].age, &temp_in[i].money);
    }
    sort(temp_in.begin(), temp_in.end(), cmp); // 排序
    vector<int> book(201, 0);
    vector<Person> people;
    for (int i = 0; i < n; i++)
    {
        if (book[temp_in[i].age] < 100) // 每个年龄都不超过 100 人
        {
            people.push_back(temp_in[i]); // 缩小数据放到新数组
            book[temp_in[i].age]++;
        }
    }
    int m, Amin, Amax; // 将循环输入的变量放到循环外减少语句量
    for (int i = 0; i < k; i++)
    {
        scanf("%d %d %d", &m, &Amin, &Amax);
        vector<Person> temp_out;
        for (int j = 0; j < people.size(); j++)
        {
            if (people[j].age >= Amin && people[j].age <= Amax)
            {
                temp_out.push_back(people[j]); // 将符合条件的放入输出数组
            }
        }
        printf("Case #%d:\n", i + 1);
        bool flag = false;
        for (int l = 0; l < m && l < temp_out.size(); l++) // 有不足 m 的情况，加一个大小的判断条件
        {
            printf("%s %d %d\n", temp_out[l].name, temp_out[l].age, temp_out[l].money);
            flag = true;
        }
        if (!flag)
        {
            printf("None\n");
        }
    }

    system("pause");
    return 0;

}

1075

题目：PAT Judge

The ranklist of PAT is generated from the status list, which shows the scores of the submissions. 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 (≤10^4)$, the total number of users, $K (≤5)$, the total number of problems, and $M (≤10^5)$, the total number of submissions. 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 submission in the following format:

user_id problem_id partial_score_obtained

where partial_score_obtained is either −1 if the submission 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 -

思路： 创建一个 N 人的结构体数组，输入时直接以 ID 作为下标进行输入

• 结构体进行存储，需要自行添加的变量有： isShow只要有一条通过编译，置为 true 表示可以输出； passnum表示满分题目数量

• 输入记录时会有一个人重复提交的情况，每次比对相同 ID 是不现实的，直接创建一个数据规模为 $N+1$ 的结构体数组，以 ID 作为下标进行记录提交处理

• 输入的成绩不止未通过和有成绩两种状态，还有未提交的情况，将成绩的初始值置为 -2 表示未提交

• 记录输入完成根据有效成绩，计算 total_score 和 passnum

• 进行排序后为每名同学赋值 rank，然后判断 isShow 的值循环输出

代码：

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

int n, k, m; // 总人数，问题数和提交记录的数量
struct Record
{
    int rank, Id, passnum = 0;              //passnum 表示完美通过的数量
    int score[6] = {0, -2, -2, -2, -2, -2}; //-2== 没有提交过；-1== 没通过编译
    bool isShow = false;                    // 若没有一条能够通过编译不显示
};

bool cmp(Record a, Record b)
{
    if (a.score[0] != b.score[0])
    {
        return a.score[0] >= b.score[0];
    }
    else if (a.passnum != b.passnum)
    {
        return a.passnum >= b.passnum;
    }
    else
    {
        return a.Id < b.Id;
    }
}

int main()
{
    scanf("%d %d %d", &n, &k, &m);
    vector<Record> v(n + 1);     // 输入记录的时候遍历寻找是哪个人进行提交是不现实的，直接用 ID 作为下标
    int full_score[k];           // 保存每道题目的成绩上限
    for (int i = 1; i <= k; i++) // 题号从 1 开始
    {
        scanf("%d", &full_score[i]); // 输入每一题的满分
    }
    int Id, pro_num, score_obt;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &Id, &pro_num, &score_obt);
        v[Id].Id = Id;
        v[Id].score[pro_num] = max(v[Id].score[pro_num], score_obt); // 多次提交保留最大值
        if (score_obt != -1)                                         // 只要有成绩就置为可以输出
        {
            v[Id].isShow = true;
        }
    } // 输入处理完成

    for (int i = 1; i <= n; i++) // 学生的序号一直到 n
    {
        for (int j = 1; j <= k; j++) // 题目的序号一直到 k
        {
            if (v[i].score[j] != -2 && v[i].score[j] != -1)
            {
                v[i].score[0] += v[i].score[j]; // 相加有效成绩
            }
            if (v[i].score[j] == full_score[j])
            {
                v[i].passnum++; // 记录满分数量
            }
        }
    }
    sort(v.begin() + 1, v.end(), cmp); //0 恒为空值
    for (int i = 1; i <= n; i++)       // 赋予排名
    {
        v[i].rank = i;
        if (i != 1 && v[i].score[0] == v[i - 1].score[0])
        {
            v[i].rank = v[i - 1].rank;
        }
    } // 处理完成

    for (int i = 1; i <= n; i++)
    {
        if (v[i].isShow) // 判断有无输出条件按格式输出
        {
            printf("%d %05d %d", v[i].rank, v[i].Id, v[i].score[0]);
            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] == -2)
                    printf(" -");
                else
                    printf(" 0");
            }
            printf("\n");
        }
    }
    system("pause");
    return 0;
}

1083

题目：List Grades

Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval.

Input Specification:

Each input file contains one test case. Each case is given in the following format:

N
name[1] ID[1] grade[1]
name[2] ID[2] grade[2]
... ...
name[N] ID[N] grade[N]
grade1 grade2

where name[i] and ID[i] are strings of no more than 10 characters with no space, grade[i] is an integer in $[0, 100]$, grade1 and grade2 are the boundaries of the grade’s interval. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case you should output the student records of which the grades are in the given interval [grade1 , grade2 ] and are in non-increasing order. Each student record occupies a line with the student’s name and ID, separated by one space. If there is no student’s grade in that interval, output NONE instead.

Sample Input 1:

4
Tom CS000001 59
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
60 100

Sample Output 1:

Mike CS991301
Mary EE990830
Joe Math990112

Sample Input 2:

2
Jean AA980920 60
Ann CS01 80
90 95

Sample Output 2:

NONE

思路： 输入完成后根据区间判断，记录符合范围的个数，不符合将值改为 -1，排序输出

代码：

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

struct Student
{

    string name, Id;
    int score;

}; 

bool cmp(Student a, Student b)
{

    return a.score > b.score;

}

int main()
{

    int n;
    cin >> n;
    vector<Student> stu;
    Student temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp.name >> temp.Id >> temp.score;
        stu.push_back(temp);
    }
    int low, height;
    int count = 0;
    cin >> low >> height;
    for (int i = 0; i < stu.size(); i++)
    {
        if (stu[i].score < low || stu[i].score > height)
        {
            stu[i].score = -1;
        }
        else
        {
            count++;
        }
    }
    if (count)
    {
        sort(stu.begin(), stu.end(), cmp);
        for (int i = 0; i < count; i++)
        {
            cout << stu[i].name << " " << stu[i].Id << endl;
        }
    }
    else
    {
        cout << "NONE\n";
    }

    system("pause");
    return 0;

}

1080

题目：Graduate Admission

It is said that in 2011, there are about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Province. It would help a lot if you could write a program to automate the admission procedure.

Each applicant will have to provide two grades: the national entrance exam grade $G_E$, and the interview grade $G_I$. The final grade of an applicant is $(G_E+G_I)/2$. The admission rules are:

• The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.

• If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade $G_E$. If still tied, their ranks must be the same.

• Each applicant may have K choices and the admission will be done according to his/her choices: if according to the rank list, it is one’s turn to be admitted; and if the quota of one’s most preferred shcool is not exceeded, then one will be admitted to this school, or one’s other choices will be considered one by one in order. If one gets rejected by all of preferred schools, then this unfortunate applicant will be rejected.

• If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.

Input Specification:

Each input file contains one test case.Each case starts with a line containing three positive integers: $N (≤40,000)$, the total number of applicants; $M (≤100)$, the total number of graduate schools; and $K(≤5)$, the number of choices an applicant may have.

In the next line, separated by a space, there are M positive integers. The i-th integer is the quota of the i-th graduate school respectively.

Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicant’s $G_E$ and $G_I$, respectively. The next K integers represent the preferred schools. For the sake of simplicity, we assume that the schools are numbered from 0 to M−1, and the applicants are numbered from 0 to N−1.

Output Specification:

For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants’ numbers that school admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.

Sample Input:

11 6 3
2 1 2 2 2 3
100 100 0 1 2
60 60 2 3 5
100 90 0 3 4
90 100 1 2 0
90 90 5 1 3
80 90 1 0 2
80 80 0 1 2
80 70 1 3 2
70 80 1 2 3
100 100 0 2 4

Sample Output:

0 10
3
5 6 7
2 8
1 4

思路： 同时建立学生学校两个结构体分别进行处理

• 学校结构体创建一个 last 变量，方便比对招满后最后一人的排名是否有与之并列的存在

• 学生结构体创建 ID 变量和 rank 保存原始编号和排名

• 按成绩排序分配排名后，对每个学生进行处理，遍历每个学生的志愿，判断是否达到入校条件

• 对每个学校的招入名单排序输出

代码：

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

struct School
{
    int quota, last;   //last 为录取的最后一个学生用来判断同排名
    vector<int> admit; // 被录取的学生放到该数组
} school[100];

struct Applicant
{
    int Id, rnk, Ge, Gi, G; // 学生 ID 要单独保存
    int choice[5];
} alct[40000];

int N, M, K;
bool cmp(Applicant a, Applicant b)
{
    if (a.G != b.G)
    {
        return a.G > b.G;
    }
    return a.Ge > b.Ge;
}

int main()
{
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++)
    {
        cin >> school[i].quota; // 输入每个学校的招生人数
    }
    for (int i = 0; i < N; i++)
    {
        cin >> alct[i].Ge >> alct[i].Gi;
        for (int j = 0; j < K; j++)
        {
            cin >> alct[i].choice[j];
        }
        alct[i].G = alct[i].Ge + alct[i].Gi; // 相加即可
        alct[i].Id = i;                      // 将编号保存，排序后仍使用原始编号
    }
    sort(alct, alct + N, cmp); // 将学生按成绩排名
    for (int i = 0; i < N; i++)
    {
        if (i == 0 || alct[i].G != alct[i - 1].G || alct[i].Ge != alct[i - 1].Ge)
        { // 分配名次
            alct[i].rnk = i + 1;
        }
        else
        {
            alct[i].rnk = alct[i - 1].rnk;
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < K; j++)
        {
            int k = alct[i].choice[j]; // 遍历所有志愿
            if (school[k].admit.size() < school[k].quota || alct[i].rnk == alct[school[k].last].rnk)
            {                                          // 人数没招满或与招到最后一人的排名相等
                school[k].admit.push_back(alct[i].Id); //ID 放入数组
                school[k].last = i;                    // 覆盖最后值
                break;
            }
        }
    }
    for (int i = 0; i < M; i++)
    {
        sort(school[i].admit.begin(), school[i].admit.end()); // 对每个学校照到的学生按序号排序
        for (int j = 0; j < school[i].admit.size(); j++)
        {
            if (j)
            { // 不是第一个就输出空格
                cout << " ";
            }
            cout << school[i].admit[j];
        }
        cout << endl;
    }

    system("pause");
    return 0;
}

1095

题目：Cars on Campus

Zhejiang University has 8 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers $N(≤10^4)$, the number of records, and $K (≤8×10^4)$ the number of queries. Then N lines follow, each gives a record in the format:

plate_number hh:mm:ss status

where plate_number is a string of 7 English capital letters or 1-digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59 ; and status is either in or out .

Note that all times will be within a single day. Each in record is paired with the chronologically next record for the same car provided it is an out record. Any in records that are not paired with an out record are ignored, as are out records not paired with an in record. It is guaranteed that at least one car is well paired in the input, and no car is both in and out at the same moment. Times are recorded using a 24-hour clock.

Then K lines of queries follow, each gives a time point in the format hh:mm:ss . Note: the queries are given in ascending order of the times.

Output Specification:

For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.

Sample Input:

16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00

Sample Output:

1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09

思路： 使用 MAP 集合存储数据，车牌号为键，结构体数组为值

• 使用结构体对出入记录进行存储，同时计算记录是在一天中的第几秒

• 遍历集合，将每个车牌对应的记录数组进行排序，进行出入配对，将当前时间点放入出入数组中，并累积一个车牌号停车的时长

• 遍历一天中的 86400 秒，将每秒的停车数量记录下来，公式：时间点前的所有进减去所有出

• 比较所有时长取出停车时间最长的，并列也放入数组，然后对车牌号排序

代码：

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

struct Record
{

    string p_num, statu;
    int hour, mintue, second, time; // 存储当前时间点在一天中是第多少秒

}; 
unordered_map<string, vector<Record>> msvr; // 记录集合
unordered_map<string, int> msi; // 停靠时间集合
int N, K; 
int in_school[86400] = {0}; // 在这一秒有多少车辆进入
int out_school[86400] = {0}; // 在这一秒有多少车辆出去

bool cmp(Record a, Record b)
{

    return a.time < b.time; // 时间从早到晚排序

}

int main()
{

    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        Record temp;
        cin >> temp.p_num;
        scanf("%d:%d:%d", &temp.hour, &temp.mintue, &temp.second);
        cin >> temp.statu;
        temp.time = temp.hour * 3600 + temp.mintue * 60 + temp.second;
        msvr[temp.p_num].push_back(temp); // 将每次输入的记录放到车牌号对应的数组中
    }
    for (auto it : msvr) // 遍历集合
    {
        auto v = it.second; // 将每个车牌号对应的数组取出
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < v.size();)
        {
            if (v[i].statu == "in") // 进行配对处理
            {
                if (i + 1 < v.size() && v[i + 1].statu == "out")
                {
                    in_school[v[i].time]++; // 将 in 的状态放到对应的时间点
                    out_school[v[i + 1].time]++;
                    msi[it.first] += v[i + 1].time - v[i].time; // 统计停车时长
                    i += 2;                                     // 下一组
                }
                else
                {
                    i++;
                }
            }
            else
            {
                i++;
            }
        }
    }

    int car_cnt[86400];
    int t = 0;
    for (int i = 0; i < 86400; i++)
    {
        t += in_school[i];
        t -= out_school[i];
        car_cnt[i] = t; // 每个时间的车辆 == 之前所有的进 - 所有的出
    }

    int t_h, t_m, t_s; 
    for (int i = 0; i < K; i++)
    {
        scanf("%d:%d:%d", &t_h, &t_m, &t_s); 
        printf("%d\n", car_cnt[t_h * 3600 + t_m * 60 + t_s]); 
    }
    int max_time = 0; 
    vector<string> maxcars; // 存储并列的最久车辆，保存车牌号
    for (auto it : msi)
    {
        if (it.second > max_time)
        {
            max_time = it.second; 
            maxcars = {it.first}; // 现在是唯一的答案，直接赋值（不使用放入，因为每次赋值都要清空前面所有的）
        }
        else if (it.second == max_time)
        {
            maxcars.push_back(it.first); // 现在是并列的答案，放入
        }
    }
    sort(maxcars.begin(), maxcars.end()); // 根据字符排序
    for (string each : maxcars)
    {
        cout << each << " "; 
    }
    printf("%02d:%02d:%02d", max_time / 3600, max_time / 60 % 60, max_time % 60); 

    system("pause");
    return 0;

}

总结

1. 如果需要对排序进行查询，一定要数据全部处理完成后再放入 MAP 集合或其他容器中，不然会导致下标混乱，如 T1012
2. 排序型算法要处理的数据难免过大，可以采用以下方式缩小复杂度：
   • 将局部变量定义在循环外，尽量缩小循环内的执行语句量
   • 输入输出函数使用 scanf() 和 printf()，字符串可以使用字符数组，排序使用 strcmp() 函数
   • 局部多次排序可以使用单次排序，尤其对大型数据的小型查询，如 T1028
3. 循环中进行比较的动态数组，不要直接放入，存在每次比较过后要清空之前数据的可能，直接赋值，如 T095

散列

思想解释

将元素通过某种方式转换为整数使其尽量唯一的表示这个元素的特质

如：求在长度为 N 的数组中，求 M 个数有没有出现过，就可以设置一个 judge[] 以 Ni 作为下标，将值置为 true，查询时只需判断 Mi 作为下标时值是否为 true 即可

将直接输入的数作为数组下标直接表示这个数的特质的方式经常使用

类型练习

1084

题目：Broken Keyboard

On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.

Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.

Input Specification:

Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typed-out string. Each string contains no more than 80 characters which are either English letters $[A-Z]$ (case insensitive), digital numbers $[0-9]$, or _ (representing the space). It is guaranteed that both strings are non-empty.

Output Specification:

For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.

Sample Input:

7_This_is_a_test
_hs_s_a_es

Sample Output:

7TI

思路：

1. 字符串写法：遍历预想字符串的每个字符去实际字符串中查找，如果本身和它大写形式查找的返回值都是string::npos，保留其大写形式

2. 散列写法：设立一个标记数组（字符会自动转为 ASCII 码作为数字下标），遍历预想字符串，如果不相同且没被标记过，放入数组

代码：

#include <iostream>
#include <cctype>
#include <vector>
using namespace std;

int main()
{
    /* 字符串写法
    string s1, s2, ans;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++) // 遍历字符串 1 中的每个字符去字符串 2 中查找
        if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)
        { // 查找字符和字符的大写，查找失败返回 string::npos
            ans += toupper(s1[i]);
        }
    cout << ans;
    */
    int flag[128] = {0};
    vector<char> vc;
    string s1, s2;
    cin >> s1 >> s2;
    int i = 0, j = 0;
    while (i < s1.length()) // 遍历全部的预想结果
    {
        if (s1[i] != s2[j])
        {
            if (!flag[s1[i]]) // 还没有标记过
            {
                flag[tolower(s1[i])] = 1;
                flag[toupper(s1[i])] = 1;     // 将大小写全部标记成 1
                vc.push_back(toupper(s1[i])); // 放入大写形式
            }
            i++;
        }
        else
        {
            i++;
            j++;
        }
    }
    for (char i : vc)
    {
        cout << i;
    }
    system("pause");
    return 0;
}

1092

题目：To Buy or Not to Buy

Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence Eva must check whether a string in the shop contains all the beads she needs. She now comes to you for help: if the answer is Yes , please tell her the number of extra beads she has to buy; or if the answer is No , please tell her the number of beads missing from the string.

For the sake of simplicity, let’s use the characters in the ranges $[0-9]$, $[a-z]$, and $[A-Z]$ to represent the colors. For example, the 3rd string in Figure 1 is the one that Eva would like to make. Then the 1st string is okay since it contains all the necessary beads with 8 extra ones; yet the 2nd one is not since there is no black bead and one less red bead.

Input Specification:

Each input file contains one test case. Each case gives in two lines the strings of no more than 1000 beads which belong to the shop owner and Eva, respectively.

Output Specification:

For each test case, print your answer in one line. If the answer is Yes , then also output the number of extra beads Eva has to buy; or if the answer is No , then also output the number of beads missing from the string. There must be exactly 1 space between the answer and the number.

Sample Input 1:

ppRYYGrrYBR2258
YrR8RrY

Sample Output 1:

Yes 8

Sample Input 2:

ppRYYGrrYB225
YrR8RrY

Sample Output 2:

No 2

思路： 使用数组或集合对每个颜色的个数进行记录，减去需要购买的值（且个数不为 0），不存在将 lack++；根据 lack 进行输出

代码：

#include <iostream>
#include <unordered_map>
using namespace std; 

int main()
{

    unordered_map<char, int> mci;
    string str1, str2;
    cin >> str1 >> str2;
    /* 数组下标标记法
    int book[256];
    for (int i = 0; i < str1.length(); i++)
        book[str1[i]]++;
    int result = 0;
    for (int i = 0; i < str2.length(); i++)
    {
        if (book[str2[i]] > 0)
            book[str2[i]]--;
        else
            result++;
    }
    */
    // 集合标记
    for (int i = 0; i < str1.length(); i++)
    {
        if (mci.count(str1[i]))
        {
            mci[str1[i]]++;
        }
        else
        {
            mci[str1[i]] = 1;
        }
    }
    int lack = 0;
    for (int i = 0; i < str2.length(); i++)
    {
        if (mci.count(str2[i]) && mci[str2[i]] != 0)
        {
            mci[str2[i]]--;
        }
        else
        {
            lack++;
        }
    }
    if (!lack)
    {
        cout << "Yes " << str1.length() - str2.length();
    }
    else
    {
        cout << "No " << lack;
    }

    system("pause");
    return 0;

}

1041

题目：Be Unique

Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from $[1,10^4]$. The first one who bets on a unique number wins. For example, if there are 7 people betting on {5 31 5 88 67 88 17}, then the second one who bets on 31 wins.

Input Specification:

Each input file contains one test case. Each case contains a line which begins with a positive integer $N (≤10^5)$ and then followed by N bets. The numbers are separated by a space.

Output Specification:

For each test case, print the winning number in a line. If there is no winner, print None instead.

Sample Input 1:

7 5 31 5 88 67 88 17

Sample Output 1:

31

Sample Input 2:

5 888 666 666 888 888

Sample Output 2:

None

思路： 使用两个数组分别记录个数和输入顺序

代码：

#include <iostream>
using namespace std;

int flag[100001] = {0}, num[100000]; //flag 进行个数统计，num 记录输入顺序
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
        flag[num[i]]++; // 将输入的数作为下标自增
    }
    bool f = true; // 判断是否有符合条件的值输出
    for (int i = 0; i < n; i++)
    {
        if (flag[num[i]] == 1)
        {
            cout << num[i];
            f = false; // 有输出
            break;
        }
    }
    if (f)
    {
        cout << "None";
    }
    system("pause");
    return 0;
}

1050

题目：String Subtraction

Given two strings S1 and S2, $S=S1−S2$ is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate $S1−S2$ for any given strings. However, it might not be that simple to do it fast.

Input Specification:

Each input file contains one test case. Each case consists of two lines which gives S1 and S2, respectively. The string lengths of both strings are no more than $10^4$. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

Output Specification:

For each test case, print $S1−S2$ in one line.

Sample Input:

They are students.
aeiou

Sample Output:

Thy r stdnts.

思路： 使用数组以字符的 ASCII 码为下标标记 S1 中每个出现的字符值为 1，S2 出现的字符置为 0，遍历 S1 只输出标记数组值为 1 的字符

代码：

#include <iostream>
using namespace std; 

int flag[256] = {0}; 
int main()
{

    string str1, str2; 
    getline(cin, str1); 
    getline(cin, str2); 
    for (int i = 0; i < str1.length(); i++)
    {
        flag[str1[i]] = 1; 
    }
    for (int i = 0; i < str2.length(); i++)
    {
        flag[str2[i]] = 0; 
    }
    for (int i = 0; i < str1.length(); i++)
    {
        if (flag[str1[i]])
        {
            cout << str1[i]; 
        }
    }

    system("pause");
    return 0;

}

1048

题目：Find Coins

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as $10^5$ coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: $N (≤10^5$, the total number of coins) and $M(≤10^3$, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the two face values V1 and V2 (separated by a space) such that $V1+V2=M$ and $V1≤V2$. If such a solution is not unique, output the one with the smallest V1. If there is no solution, output No Solution instead.

Sample Input 1:

8 15
1 2 8 7 2 4 11 15

Sample Output 1:

4 11

Sample Input 2:

7 14
1 8 7 2 4 11 15

Sample Output 2:

No Solution

思路： 使用数组标记每个面值出现的次数，然后从 1 到 bill 对每一个面值进行遍历（规则就是从小到大），判断输出

代码：

#include <iostream>
using namespace std;

int flag[1001] = {0}; // 用来统计每个面值出现了几次
int main()
{
    int n, m, temp;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        flag[temp]++;
    }
    for (int i = 1; i < m; i++) // 对每个面值的硬币从小到大判断（保证输出规则）
    {
        if (flag[i]) // 当前面值存在
        {
            flag[i]--;       // 存在就 -1，防止出现一个数出现了一次但它的二倍等于 bill
            if (flag[m - i]) // 符合相加条件的硬币也存在
            {
                cout << i << " " << m - i; // 输出
                system("pause");
                return 0;
            }
            flag[i]++;
        }
    }
    cout << "No Solution";
    system("pause");
    return 0;
}

贪心

思想解释

总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择

类型练习

1070

题目：Mooncake

Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the region’s culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.

Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is $7.2 + 4.5/2 = 9.45$ (billion yuans).

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers $N(≤1000)$, the number of different kinds of mooncakes, and $D(≤500$ thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) of N kinds of mooncakes. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.

Sample Input:

3 200
180 150 100
7.5 7.2 4.5

Sample Output:

9.45

思路： 使用结构体放入数组，根据单价排序，循环判断需求量计算收益

代码：

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

struct Mooncake
{

    double quality, single_price, total_price; // 全国用 double 型，防止精确度不够

}; 

int N, D; 
bool cmp(Mooncake a, Mooncake b) // 按单价排序
{

    return a.single_price > b.single_price;

}

int main()
{

    cin >> N >> D; 
    vector<Mooncake> mc(N); 
    for (int i = 0; i < N; i++)
    {
        cin >> mc[i].quality; 
    }
    for (int i = 0; i < N; i++)
    {
        cin >> mc[i].total_price; 
        mc[i].single_price = mc[i].total_price / mc[i].quality; 
    }
    sort(mc.begin(), mc.end(), cmp); // 输入后按照单价进行排序
    double profit = 0.0; 
    int i = 0; 
    while (D && i < mc.size()) // 注意可能存在所有种类的总量不够需求量的情况
    {
        if (D > mc[i].quality)
        {
            profit += mc[i].total_price; // 需求量仍超过当前种类的质量
        }
        else
        {
            profit += D * mc[i].single_price; // 不足将剩余量乘单价
            break; 
        }
        D -= mc[i].quality; // 去掉已经购买的
        i++; // 判断下一组
    }
    printf("%.2f", profit); 

    system("pause");
    return 0;

}

1033

题目：To Fill or Not to Fill

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: $Cmax (≤ 100)$, the maximum capacity of the tank; $D(≤30000)$, the distance between Hangzhou and the destination city; $Davg (≤20)$, the average distance per unit gas that the car can run; and $N(≤ 500)$, the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and $D_i(≤D)$, the distance between this station and Hangzhou, for $i=1,⋯,N$. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

思路： 将终点也作为加油站的形式进行存储，对所有的加油站按照距离进行排序，每次从起点判断满油状态下可以到达的加油站中油价最便宜的一个，根据价格进行不同的处理

代码：

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct station // 加油站的结构体
{
    double price, distance;
};

double Cmax, D, Davg;
int N;
station sta[501];

bool cmp(station a, station b) // 将所有加油站按距离排序
{
    return a.distance < b.distance;
}

int main()
{
    cin >> Cmax >> D >> Davg >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> sta[i].price >> sta[i].distance;
    }
    sta[N].price = 0;
    sta[N].distance = D;     // 将终点作为加油站的形式方便循环处理
    sort(sta, sta + N, cmp); // 按距离排序

    if (sta[0].distance != 0) // 如果起点位置没有加油站
    {
        cout << "The maximum travel distance = 0.00";
    }
    else
    {
        int now = 0;
        double ans = 0, nowTank = 0, max_dis = Cmax * Davg;
        while (now < N) // 循环模拟每一个站
        {
            int k = -1;
            double minP = INT_MAX;
            for (int i = now + 1; i <= N && sta[i].distance - sta[now].distance <= max_dis; i++)
            { // 循环判断满油状态下的最长距离中油价最便宜的一个站
                if (sta[i].price < minP)
                {
                    minP = sta[i].price;
                    k = i;
                    if (minP < sta[now].price)
                    {
                        break;
                    }
                }
            }
            if (k == -1) // 没找到跳出
            {
                break;
            }
            double need = (sta[k].distance - sta[now].distance) / Davg; // 到最便宜站需要加的油
            if (minP <= sta[now].price)                                 // 又可以到达价格小于当前的站
            {
                if (nowTank < need) // 当前油箱无法到达
                {
                    ans += (need - nowTank) * sta[now].price;
                    nowTank = 0;
                }
                else
                {
                    nowTank -= need;
                }
            }
            else
            {
                ans += (Cmax - nowTank) * sta[now].price;
                nowTank = Cmax - need;
            }
            now = k;
        }
        if (now == N)
        {
            printf("%.2f", ans);
        }
        else
        {
            printf("The maximum travel distance = %.2f", sta[now].distance + max_dis);
        }
    }

    system("pause");
    return 0;
} 

1037

题目：Magic Coupon

The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!

For example, given a set of coupons {1 2 4 −1}, and a set of product values {7 6 −2 −3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.

Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

Input Specification:

Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here $1≤N_C, N_P≤10^5$, and it is guaranteed that all the numbers will not exceed $2^{30}$.

Output Specification:

For each test case, simply print in a line the maximum amount of money you can get back.

Sample Input:

4
1 2 4 -1
4
7 6 -2 -3

Sample Output:

43

思路： 将两组数据放入两个数组，将数据从小到大排序，负数从小到大分别相乘，正数从大到小分别相乘，0 不做处理

代码：

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

int main()
{

    int n, m; 
    cin >> n; 
    vector<int> coupon(n); 
    for (int i = 0; i < n; i++)
    {
        cin >> coupon[i]; 
    }
    cin >> m; 
    vector<int> product(m); 
    for (int i = 0; i < m; i++)
    {
        cin >> product[i]; 
    }
    sort(coupon.begin(), coupon.end()); 
    sort(product.begin(), product.end()); // 将数组从小到大排序
    int i = 0, j = 0, ans = 0; 
    while (i < n && j < m && coupon[i] < 0 && product[j] < 0) // 处理负数
    {
        ans += coupon[i] * product[j]; 
        i++; 
        j++; 
    }
    i = n - 1; 
    j = m - 1; 
    while (i >= 0 && j >= 0 && coupon[i] > 0 && product[j] > 0) // 处理正数
    {
        ans += coupon[i] * product[j]; 
        i--; 
        j--; 
    }
    cout << ans; 

    system("pause");
    return 0;

}

1067

题目：Sort with Swap(0, i)

Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive $N(≤10^5)$ followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10
3 5 7 2 6 4 9 0 8 1

Sample Output:

9

思路： 使用数字作为下标顺序，作为位置的方式存储数组，当每个位置上数字与位置相同表示交换完毕（这样无需进行下标查找）

• 遍历位置与数字是否对应，当不对应且 0 未处于排列首位时交换 0 与本该在 0 的位置上的数字 swap(per[0], per[per[0]]);

• 当 0 回到首位继续判断位置是否对应，若未成功将 0 换到不对应的位置继续判断操作

代码：

#include <iostream>
using namespace std; 

int main()
{

    int n; 
    cin >> n; 
    int per[n], temp, ans = 0; 
    for (int i = 0; i < n; i++)
    {
        cin >> temp; // 将输入的数作为下标，第几次输入作为位置
        per[temp] = i; 
    }
    for (int i = 0; i < n; i++)
    {
        if (i != per[i]) // 当各个数字没有归位
        {
            while (per[0] != 0) //0 没有归位便进行调换
            {
                swap(per[0], per[per[0]]); // 将 0 所在的位置和其应当存在的的数进行交换
                ans++; 
            }
            if (i != per[i]) // 一轮调换未能匹配，将 0 换入不匹配的位置
            {
                swap(per[0], per[i]); 
                ans++; 
            }
        }
    }
    cout << ans; 

    system("pause");
    return 0;

}

1038

题目：Recover the Smallest Number

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given
{$32, 321, 3214, 0229, 87$}, we can recover many numbers such like $32-321-3214-0229-87$ or $0229-32-87-321-3214$ with respect to different orders of combinations of these segments, and the smallest number is $0229-321-3214-32-87$.

Input Specification:

Each input file contains one test case. Each case gives a positive integer $N (≤10^4)$ followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the smallest number in one line. Notice that the first digit must not be zero.

Sample Input:

5 32 321 3214 0229 87

Sample Output:

22932132143287

思路： 采用字符串进行读取，定义一个等式相加的排序规则

代码：

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

bool cmp(string a, string b)
{
    return a + b < b + a; // 如果 a+b<b+a，a 就在前面，否则反之
}

int main()
{
    int n;
    cin >> n;
    string str[n];
    for (int i = 0; i < n; i++)
    {
        cin >> str[i];
    }
    sort(str, str + n, cmp);
    string ans;
    for (int i = 0; i < n; i++)
    {
        ans += str[i]; // 拼接排序后的字符数组
    }
    while (ans.length() != 0 && ans[0] == '0') // 去掉前导零
    {
        ans.erase(ans.begin());
    }
    if (ans.length() == 0)
    {
        cout << 0;
    }
    else
    {
        cout << ans;
    }

    system("pause");
    return 0;
}

二分

思想解释

在有序的排列中，根据目标值 goal 与中间值 mid ($mid=(end+begin)/2$) 的大小关系不断缩小范围的查找方式

mid 的求值：有些数据长度过大，导致 $end+begin$ 超出当前数据类型的范围，可以采用 $mid=begin+(end-begin)/2$ 的式子

常使用 [algorithm] 下的 upper_bound(lower_bound) 和 binary_search 方法

类型练习

1085

题目：Perfect Sequence

Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if $M≤m×p$ where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where $N (≤10^5)$ is the number of integers in the sequence, and $p (≤10^9)$ is the parameter. In the second line there are N positive integers, each is no greater than $10^9$.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:

8

思路： 将输入的数据从小到大排序，遍历每一个数将它作为 m 计算 M，使用 upper_bound() 函数求出 完美队列 的长度，取长度最大值

注意：数据范围为 $10^9$那么 $m×p$可能溢出 int 型，所以使用 long long 强转

代码：

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

int main()
{

    int n, p; 
    cin >> n >> p; 
    int arr[n]; 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i]; 
    }
    sort(arr, arr + n); // 从小到大排序
    int ans = 1; 
    for (int i = 0; i < n; i++)
    { // 从数组的开始每次找一个数作为 m 进行判断
        int bound = upper_bound(arr, arr + n, (long long)arr[i] * p) - arr; 
        //arr[i] 作为 m 时符合完美队列条件的长度
        ans = max(ans, bound - i); // 保留最大长度
    }
    cout << ans; 

    system("pause");
    return 0;

}

1010

题目：Radix

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers $N1$ and $N2$, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

思路： 将确定进制的数转换为十进制，将为判断的数采用二分法来确定进制；一个数的进制越大，转换为十进制的结果越大：101 的二进制为 5，但十六进制为 272

• 编写一个转换函数，其中要解决字符映射问题，手动转换十进制思路：反向循环相加 当前数×指数的位数幂

• 编写查找进制函数，其中要解决的时上下界的确定，下界 low 为单个位最大数 +1，上界 height 位 max(low, 要求数字的十进制），每次二分 $binary(low,height)$作为指数转换为十进制，如果得到的数为负数（过大溢出）或超过要求数字的十进制，表示当前进制过大，否者过小，每次更换范围，直到相等

代码：

#include <iostream>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;

long long convert(string str, long long radix)
{ // 将已经确定进制的数转换为十进制
    int decimal = 0;
    int temp = 0, index = 0;
    for (auto it = str.rbegin(); it != str.rend(); it++)
    {
        temp = isdigit(*it) ? *it - '0' : *it - 'a' + 10;
        decimal += temp * pow(radix, index++);
    }
    return decimal;
}

long long findresult(string str, long long decimal)
{
    char it = *max_element(str.begin(), str.end());// 使用函数求出 ASCII 码最大的字符
    long long low = (isdigit(it) ? it - '0' : it - 'a' + 10) + 1;// 确定下界
    long long height = max(low, decimal);// 确定上界
    while (low <= height)// 二分判断
    {
        long long mid = low + (height - low) / 2;
        long long temp = convert(str, mid);
        if (temp < 0 || temp > decimal) //t 小于 0 表示溢出
        {
            height = mid - 1;
        }
        else if (temp == decimal)
        {
            return mid;// 相等返回 mid 作为指数
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;// 不存在返回 -1
}
int main()
{
    string s1, s2;
    long long tag = 0, radix = 0, result_radix;
    cin >> s1 >> s2 >> tag >> radix;
    if (s1 == s2)// 如果输入直接相等，输出给定的指数
    {
        cout << radix;
    }
    else
    {
        result_radix = (tag == 1) ? findresult(s2, convert(s1, radix)) : findresult(s1, convert(s2, radix));
        if (result_radix == -1)
        {
            cout << "Impossible";
        }
        else
        {
            cout << result_radix;
        }
    }

    system("pause");
    return 0;
}

1044

题目：Shopping in Mars

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M $3, 2, 1, 5, 4, 6, 8, 7$, and we must pay M 15. We may have 3 options:

1. Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5
   with values $3+2+1+5+4=15$

2. Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values $5+4+6=15$).

3. Cut before 8, and take off the diamonds from the position 7 to 8 (with values $8+7=15$).

Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.

If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤105), the total number of diamonds on the chain, and $M (≤10^8)$, the amount that the customer has to pay. Then the next line contains N positive numbers $D1⋯DN (Di≤10^3 for all i=1, ⋯, N)$ which are the values of the diamonds. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print i-j in a line for each pair of i ≤ j such that D i + … + D j = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i .

If there is no solution, output i-j for pairs of i ≤ j such that D i + … + D j >M with (D i + … + D j −M) minimized. Again all the solutions must be printed in increasing order of i .

It is guaranteed that the total value of diamonds is sufficient to pay the given amount.

Sample Input 1:

16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

Sample Output 1:

1-5
4-6
7-8
11-11

Sample Input 2:

5 13
2 4 5 7 9

Sample Output 2:

2-4
4-5

思路： 序列的和是有序递增的，因此一个连续序列和的右端减去左端就是该子序列的和 (must pay)

• 对有序序列可以采用二分查找的方式，遍历左端点，二分查找右端点，查找值是 >=m，因为可能有无法匹配求最小损失的情况

• 方法函数的参数可以使用 (int i, int &j, int &tempsum)的方式直接改变 j 和 tempsum 的值

代码：

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

int n, m; 
vector<int> sum, resultArr; 
void Func(int i, int &j, int &tempsum) // 二分就目标值
{

    int left = i, right = n;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (sum[mid] - sum[i - 1] >= m) // 不一定完全匹配，求较大的最小值
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    j = right;
    tempsum = sum[j] - sum[i - 1];

}
int main()
{

    cin >> n >> m;
    sum.resize(n + 1);
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    int minans = sum[n];
    for (int i = 1; i <= n; i++) // 遍历所有数字作为左端点
    {
        int j, tempsum;
        Func(i, j, tempsum);  // 挨个二分查找
        if (tempsum > minans) // 如果过大下一次循环
        {
            continue;
        }
        if (tempsum >= m) // 符合条件
        {
            if (tempsum < minans) // 有更接近目标值的数字便更新集合
            {
                resultArr.clear();
                minans = tempsum;
            }
            resultArr.push_back(i);
            resultArr.push_back(j);
        }
    }
    for (int i = 0; i < resultArr.size(); i += 2)
    {
        cout << resultArr[i] << "-" << resultArr[i + 1] << endl;
    }

    system("pause");
    return 0;

}

双指针

思想解释

使用两个指针指向序列的不同位置，用指针的移动操作减少处理复杂度的方式
其中归并排序和快速排序都可以使用双指针的方式进行编写

• 归并排序： 常使用的多为二路归并排序，将一组数分为两两一组进行组内排序，再将每组两两合并进行排序，以此类推

• 快速排序： 每次挑选一个数字作为比较参照，将大于参照数的值放入右侧，小于放左侧

类型练习

1089

题目：Insert or Merge

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.

Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

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 “Merge 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 0 6
1 3 2 8 5 7 4 9 0 6

Sample Output 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6

思路： 先判断是否为插入排序，如果不是则一定是归并排序

• 建立两个初始数组，和目标数组，初始数组中一个用于插入排序，一个用于归并排序

• 注意初始数组不能直接和目标数组相同，否者容易出现双解

代码：

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

int origin[100], tempOri[100], changed[100]; // 初始数组，初始备份，目标数组
int n;

bool isSame(int a[], int b[]) // 判断数组相同
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] != b[i])
        {
            return false;
        }
    }
    return true;
}

void showArr(int a[]) // 输出方法
{
    for (int i = 0; i < n - 1; i++)
    {
        cout << a[i] << " ";
    }
    cout << a[n - 1];
}

bool insertSort() // 使用布尔型，返回 false 表示其为归并
{
    bool flag = false;
    for (int i = 1; i < n; i++) // 从第二个元素开始插入
    {
        if (i != 1 && isSame(tempOri, changed)) // 抛开第一次即相同的情况下相同
        {
            flag = true; // 判断相同再排序一次，方便输出 next 序列
        }
        // 插入排序核心代码
        int j = i, temp = tempOri[i];
        while (j != 0 && tempOri[j - 1] > temp)
        {
            tempOri[j] = tempOri[j - 1];
            j--;
        }
        tempOri[j] = temp;

        if (flag) // 当判断成功直接跳出
        {
            break;
        }
    }
    return flag;
}

void mergeSort() // 不是插入排序直接使用归并方法
{
    bool flag = false;
    for (int step = 2; step / 2 <= n; step *= 2) // 归并的遍历方式
    {
        if (step != 2 && isSame(origin, changed)) // 抛开第一次即相同的情况下相同
        {
            flag = true;
        }
        for (int i = 0; i < n; i += step) // 对每组进行排序
        {
            sort(origin + i, origin + min(i + step, n)); // 直接使用 sort 方法即可
        }
        if (flag)
        {
            showArr(origin);
            break; // 在循环中结束记得跳出
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> origin[i];
        tempOri[i] = origin[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> changed[i];
    }

    if (insertSort())
    {
        cout << "Insertion Sort" << endl;
        showArr(tempOri);
    }
    else
    {
        cout << "Merge Sort" << endl;
        mergeSort();
    }

    system("pause");
    return 0;
}

1029

** 题目：Median **

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of $S1 = {11, 12, 13, 14}$ is 12, and the median of $S2 = {9, 10, 15, 16, 17}$ is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer $N (≤2×10^5)$ is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output Specification:

For each test case you should output the median of the two given sequences in a line.

Sample Input:

4 11 12 13 14
5 9 10 15 16 17

Sample Output:

13

思路： 只需要输出中位数而无需对整个序列进行处理，所以不必采用合并后排序的方式进行判断，使用双指针判断相应位置

• 设置 i、j 两个指针分别指向两个数组，每次判断较小值后指针后移，当后移次数为 $medianPosition=(N+M-1)÷2$输出

• 可能存在一个数组的整体数字过于小导致真个数组全部判断完成，两个指针的移动次数和还未到达中位数，所以要在数组的后边界设置一个较大数，int 型最大为 $2^{31}-1$（代码可以写作 0x7fffffff或 (1<<31)-1）的形式

• 最后到达中位位置时，两个数的值还未进行判断，再次判断指针输出较小值

代码：

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

int main()
{

    vector<int> sequeN, sequeM;
    int temp;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        sequeN.push_back(temp);
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> temp;
        sequeM.push_back(temp);
    }
    int median = (n + m - 1) / 2;
    sequeN[n] = sequeM[m] = (1 << 31) - 1;// 将数组边界设置为 2^31-1
    int i = 0, j = 0, count = 0;
    while (count < median)
    {
        if (sequeN[i] < sequeM[j])
        {
            i++;
        }
        else
        {
            j++;
        }
        count++;
    }
    if (sequeN[i] < sequeM[j])
    {
        cout << sequeN[i];
    }
    else
    {
        cout << sequeM[j];
    }

    system("pause");
    return 0;

}

其他

思想解释

• 打表： 将小范围结果计算出来，直接在程序中调用，用空间换时间
• 递推： 大部分算法都是有递推规则的，根据规则编写仅适合这一道题的程序
• 随机选择：有点玄学

类型练习

1093

题目：Count PAT’s

The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT’s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT’s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

APPAPT

Sample Output:

2

思路： 根据递推思想，组成 "PAT" 的个数就是字符’A’左边’P’的个数乘右边’T’的个数

• 遍历字符串求出每个字符左边 P 的个数

• 反向遍历，遇到 T 计数器 +1，遇到 A 累加相乘取模

代码：

#include <iostream>
using namespace std;

const int mod = 1000000007;
int main()
{
    string str;
    cin >> str;
    int len = str.length();
    int countP[100000] = {0};

    for (int i = 0; i < len; i++) // 获取每个位置左侧字符 'P' 的个数
    {
        if (i > 0)
        {
            countP[i] = countP[i - 1];
        }
        if (str[i] == 'P')
        {
            countP[i]++;
        }
    }

    int ans = 0, countT = 0;
    for (int i = len - 1; i >= 0; i--)
    {
        if (str[i] == 'T')
        {
            countT++; // 累计 T
        }
        if (str[i] == 'A') // 遇到 'A' 便相加取模
        {
            ans = (ans + countT * countP[i]) % mod;
        }
    }
    cout << ans;
    system("pause");
    return 0;
}

1101

题目：Quick Sort

There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?

For example, given N=5 and the numbers 1, 3, 2, 4, and 5. We have:

• 1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;

• 3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;

• 2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;

• and for the similar reason, 4 and 5 could also be the pivot.

Hence in total there are 3 pivot candidates.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤105). Then the next line contains N distinct positive integers no larger than 109. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:

5
1 3 2 4 5

Sample Output:

3
1 4 5

思路： 双向遍历，保留每个数字左边的最大值和右边的最小值，最后遍历判断是否大于左边最大值并小于右边最小值

代码：

#include <iostream>
using namespace std; 

int main()
{

    int n; 
    cin>>n; 
    int leftMax[n], rightMin[n], arr[n]; 
    int ans[n], num = 0; 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i]; 
    }
    leftMax[0] = 0; 
    for (int i = 1; i < n; i++)
    {
        leftMax[i] = max(leftMax[i - 1], arr[i - 1]); 
    }
    rightMin[n - 1] = 0x3fffffff; 
    for (int i = n - 2; i >= 0; i--)
    {
        rightMin[i] = min(rightMin[i + 1], arr[i + 1]); 
    }
    for (int i = 0; i < n; i++)
    {
        if (leftMax[i] < arr[i] && rightMin[i] > arr[i])
        {
            ans[num++] = arr[i]; 
        }
    }
    cout << num << endl; 
    for (int i = 0; i < num; i++)
    {
        cout << ans[i]; 
        if (i < num - 1)
        {
            cout << " "; 
        }
    }
    cout << endl; 

    system("pause");
    return 0;

}