OJ – 第8页 – liuchuo

1012. The Best Rank (25)-PAT甲级真题

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 Algebra), 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

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

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

题目大意：现已知n个考生的3门分数，平均分可以按照这三门算出来。然后分别对这四个分数从高到低排序，这样对每个考生来说有4个排名。k个查询，对于每一个学生id，输出当前id学生的最好的排名和它对应的分数，如果名次相同，按照A>C>M>E的顺序输出～如果当前id不存在，输出N/A～
分析：
1、用结构体存储学生的id、四门成绩、四门排名、最好的排名的对应的科目下标～
2、排名并列应该1、1、3、4、5，而不是1、1、2、3、4，否则会有一个测试点不过
3、平均分是四舍五入的，所以需要按照+0.5后取整，保证是四舍五入的（听说不四舍五入也能通过…）
4、存储的时候就按照ACME的顺序存储可以简化程序逻辑～
5、用exist数组保存当前id是否存在，这个id对应的stu结构体的下标是多少。用i+1可以保证为0的都是不存在的可以直接输出N/A，其余不为0的保存的值是对应的结构体index + 1的值～

#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int id, best;
    int score[4], rank[4];
}stu[2005];
int exist[1000000], flag = -1;
bool cmp1(node a, node b) {return a.score[flag] > b.score[flag];}
int main() {
    int n, m, id;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);
        stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;
    }
    for(flag = 0; flag <= 3; flag++) {
        sort(stu, stu + n, cmp1);
        stu[0].rank[flag] = 1;
        for(int i = 1; i < n; i++) {
            stu[i].rank[flag] = i + 1;
            if(stu[i].score[flag] == stu[i-1].score[flag])
                stu[i].rank[flag] = stu[i-1].rank[flag];
        }
    }
    for(int i = 0; i < n; i++) {
        exist[stu[i].id] = i + 1;
        stu[i].best = 0;
        int minn = stu[i].rank[0];
        for(int j = 1; j <= 3; j++) {
            if(stu[i].rank[j] < minn) {
                minn = stu[i].rank[j];
                stu[i].best = j;
            }
        }
    }
    char c[5] = {'A', 'C', 'M', 'E'};
    for(int i = 0; i < m; i++) {
        scanf("%d", &id);
        int temp = exist[id];
        if(temp) {
            int best = stu[temp-1].best;
            printf("%d %c\n", stu[temp-1].rank[best], c[best]);
        } else {
            printf("N/A\n");
        }
    }
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

struct node {

int id, best;

int score[4], rank[4];

}stu[2005];

int exist[1000000], flag = -1;

bool cmp1(node a, node b) {return a.score[flag] > b.score[flag];}

int main() {

int n, m, id;

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

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

scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);

stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;

}

for(flag = 0; flag <= 3; flag++) {

sort(stu, stu + n, cmp1);

stu[0].rank[flag] = 1;

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

stu[i].rank[flag] = i + 1;

if(stu[i].score[flag] == stu[i-1].score[flag])

stu[i].rank[flag] = stu[i-1].rank[flag];

}

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

exist[stu[i].id] = i + 1;

stu[i].best = 0;

int minn = stu[i].rank[0];

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

if(stu[i].rank[j] < minn) {

minn = stu[i].rank[j];

stu[i].best = j;

}

char c[5] = {'A', 'C', 'M', 'E'};

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

scanf("%d", &id);

int temp = exist[id];

if(temp) {

int best = stu[temp-1].best;

printf("%d %c\n", stu[temp-1].rank[best], c[best]);

} else {

printf("N/A\n");

}

return 0;

}

1082. Read Number in Chinese (25)-PAT甲级真题

Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output “Fu” first if it is negative. For example, -123456789 is read as “Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu”. Note: zero (“ling”) must be handled correctly according to the Chinese tradition. For example, 100800 is “yi Shi Wan ling ba Bai”.
Input Specification:
Each input file contains one test case, which gives an integer with no more than 9 digits.
Output Specification:
For each test case, print in a line the Chinese way of reading the number. The characters are separated by a space and there must be no extra space at the end of the line.
Sample Input 1:
-123456789
Sample Output 1:
Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu
Sample Input 2:
100800
Sample Output 2:
yi Shi Wan ling ba Bai

题目大意：给定一个不超过9位的整数，你应该用传统的中文方式阅读它~ 如果是负的，首先输出“Fu”。例如，-123456789被读作“Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu”。注意：零（“ling”）必须根据中国传统正确处理。例如，100800是“yi Shi Wan ling ba Bai”~

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string num[10] = { "ling","yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu" };
string c[6] = { "Ge","Shi", "Bai", "Qian", "Yi", "Wan" };
int J[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
vector<string> res;
int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << "ling";
        return 0;
    }
    if (n < 0) {
        cout << "Fu ";
        n = -n;
    }
    int part[3];
    part[0]= n / 100000000; 
    part[1]= (n % 100000000) / 10000;
    part[2] = n % 10000;
    bool zero = false; //是否在非零数字前输出合适的ling
    int printCnt = 0; //用于维护单词前没有空格，之后输入的单词都在前面加一个空格。
    for (int i = 0; i < 3; i++) {
        int temp = part[i]; //三个部分，每部分内部的命名规则都一样，都是X千X百X十X
        for (int j = 3; j >= 0; j--) {
            int curPos = 8 - i * 4 + j; //当前数字的位置
            if (curPos >= 9) continue; //最多九位数
            int cur = (temp / J[j]) % 10;//取出当前数字
            if (cur != 0) {
                if (zero) {
                    printCnt++ == 0 ? cout<<"ling" : cout<<" ling";
                    zero = false;
                }
                if (j == 0)
                    printCnt++ == 0 ? cout << num[cur] : cout << ' ' << num[cur]; //在个位，直接输出
                else                             
                    printCnt++ == 0 ? cout << num[cur] << ' ' << c[j] : cout << ' ' << num[cur] << ' ' << c[j]; //在其他位，还要输出十百千
            } else {
                if (!zero && j != 0 && n / J[curPos] >= 10) zero = true;   //注意100020这样的情况
            }
        }
        if (i != 2 && part[i]>0) cout << ' ' << c[i + 4]; //处理完每部分之后，最后输出单位，Yi/Wan
    }
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

string num[10] = { "ling","yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu" };

string c[6] = { "Ge","Shi", "Bai", "Qian", "Yi", "Wan" };

int J[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};

vector<string> res;

int main() {

int n;

cin >> n;

if (n == 0) {

cout << "ling";

return 0;

}

if (n < 0) {

cout << "Fu ";

n = -n;

}

int part[3];

part[0]= n / 100000000;

part[1]= (n % 100000000) / 10000;

part[2] = n % 10000;

bool zero = false; //是否在非零数字前输出合适的ling

int printCnt = 0; //用于维护单词前没有空格，之后输入的单词都在前面加一个空格。

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

int temp = part[i]; //三个部分，每部分内部的命名规则都一样，都是X千X百X十X

for (int j = 3; j >= 0; j--) {

int curPos = 8 - i * 4 + j; //当前数字的位置

if (curPos >= 9) continue; //最多九位数

int cur = (temp / J[j]) % 10;//取出当前数字

if (cur != 0) {

if (zero) {

printCnt++ == 0 ? cout<<"ling" : cout<<" ling";

zero = false;

}

if (j == 0)

printCnt++ == 0 ? cout << num[cur] : cout << ' ' << num[cur]; //在个位，直接输出

else

printCnt++ == 0 ? cout << num[cur] << ' ' << c[j] : cout << ' ' << num[cur] << ' ' << c[j]; //在其他位，还要输出十百千

} else {

if (!zero && j != 0 && n / J[curPos] >= 10) zero = true; //注意100020这样的情况

}

if (i != 2 && part[i]>0) cout << ' ' << c[i + 4]; //处理完每部分之后，最后输出单位，Yi/Wan

}

return 0;

}

1114. Family Property (25)-PAT甲级真题（并查集）

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother k Child1 … Childk M_estate Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0<=k<=5) is the number of children of this person; Childi’s are the ID’s of his/her children; M_estate is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

ID M AVG_sets AVG_area

where ID is the smallest ID in the family; M is the total number of family members; AVG_sets is the average number of sets of their real estate; and AVG_area is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID’s if there is a tie.

Sample Input:
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
Sample Output:
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

题目大意：给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：家庭成员的最小编号家庭人口数人均房产套数人均房产面积。其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
分析：用并查集。分别用两个结构体数组，一个data用来接收数据，接收的时候顺便实现了并查集的操作union，另一个数组ans用来输出最后的答案，因为要计算家庭人数，所以用visit标记所有出现过的结点，对于每个结点的父结点，people++统计人数。标记flag == true，计算true的个数cnt就可以知道一共有多少个家庭。排序后输出前cnt个就是所求答案～～

#include <cstdio>
#include <algorithm>
using namespace std;
struct DATA {
    int id, fid, mid, num, area;
    int cid[10];
}data[1005];
struct node {
    int id, people;
    double num, area;
    bool flag = false;
}ans[10000];
int father[10000];
bool visit[10000];
int find(int x) {
    while(x != father[x])
        x = father[x];
    return x;
}
void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA > faB)
        father[faA] = faB;
    else if(faA < faB)
        father[faB] = faA;
}
int cmp1(node a, node b) {
    if(a.area != b.area)
        return a.area > b.area;
    else
        return a.id < b.id;
}
int main() {
    int n, k, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < 10000; i++)
        father[i] = i;
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);
        visit[data[i].id] = true;
        if(data[i].fid != -1) {
            visit[data[i].fid] = true;
            Union(data[i].fid, data[i].id);
        }
        if(data[i].mid != -1) {
            visit[data[i].mid] = true;
            Union(data[i].mid, data[i].id);
        }
        for(int j = 0; j < k; j++) {
            scanf("%d", &data[i].cid[j]);
            visit[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        scanf("%d %d", &data[i].num, &data[i].area);
    }
    for(int i = 0; i < n; i++) {
        int id = find(data[i].id);
        ans[id].id = id;
        ans[id].num += data[i].num;
        ans[id].area += data[i].area;
        ans[id].flag = true;
    }
    for(int i = 0; i < 10000; i++) {
        if(visit[i])
            ans[find(i)].people++;
        if(ans[i].flag)
            cnt++;
    }
    for(int i = 0; i < 10000; i++) {
        if(ans[i].flag) {
            ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
            ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
        }
    }
    sort(ans, ans + 10000, cmp1);
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

struct DATA {

int id, fid, mid, num, area;

int cid[10];

}data[1005];

struct node {

int id, people;

double num, area;

bool flag = false;

}ans[10000];

int father[10000];

bool visit[10000];

int find(int x) {

while(x != father[x])

x = father[x];

return x;

}

void Union(int a, int b) {

int faA = find(a);

int faB = find(b);

if(faA > faB)

father[faA] = faB;

else if(faA < faB)

father[faB] = faA;

}

int cmp1(node a, node b) {

if(a.area != b.area)

return a.area > b.area;

else

return a.id < b.id;

}

int main() {

int n, k, cnt = 0;

scanf("%d", &n);

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

father[i] = i;

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

scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);

visit[data[i].id] = true;

if(data[i].fid != -1) {

visit[data[i].fid] = true;

Union(data[i].fid, data[i].id);

}

if(data[i].mid != -1) {

visit[data[i].mid] = true;

Union(data[i].mid, data[i].id);

}

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

scanf("%d", &data[i].cid[j]);

visit[data[i].cid[j]] = true;

Union(data[i].cid[j], data[i].id);

}

scanf("%d %d", &data[i].num, &data[i].area);

}

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

int id = find(data[i].id);

ans[id].id = id;

ans[id].num += data[i].num;

ans[id].area += data[i].area;

ans[id].flag = true;

}

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

if(visit[i])

ans[find(i)].people++;

if(ans[i].flag)

cnt++;

}

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

if(ans[i].flag) {

ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);

ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);

}

sort(ans, ans + 10000, cmp1);

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

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

printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);

return 0;

}

L2-007. 家庭房产-PAT团体程序设计天梯赛GPLT

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式：

输入第一行给出一个正整数N（<=1000），随后N行，每行按下列格式给出一个人的房产：

编号父母 k 孩子1 … 孩子k 房产套数总面积

其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0<=k<=5）是该人的子女的个数；孩子i是其子女的编号。

输出格式：

首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号家庭人口数人均房产套数人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

输入样例：
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
输出样例：
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

分析：用并查集。分别用两个结构体数组，一个data用来接收数据，接收的时候顺便实现了并查集的操作union，另一个数组ans用来输出最后的答案，因为要计算家庭人数，所以用visit标记所有出现过的结点，对于每个结点的父结点，people++统计人数。标记flag == true，计算true的个数cnt就可以知道一共有多少个家庭。排序后输出前cnt个就是所求答案～～

#include <cstdio>
#include <algorithm>
using namespace std;
struct DATA {
    int id, fid, mid, num, area;
    int cid[10];
}data[1005];
struct node {
    int id, people;
    double num, area;
    bool flag = false;
}ans[10000];
int father[10000];
bool visit[10000];
int find(int x) {
    while(x != father[x])
        x = father[x];
    return x;
}
void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA > faB)
        father[faA] = faB;
    else if(faA < faB)
        father[faB] = faA;
}
int cmp1(node a, node b) {
    if(a.area != b.area)
        return a.area > b.area;
    else
        return a.id < b.id;
}
int main() {
    int n, k, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < 10000; i++)
        father[i] = i;
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);
        visit[data[i].id] = true;
        if(data[i].fid != -1) {
            visit[data[i].fid] = true;
            Union(data[i].fid, data[i].id);
        }
        if(data[i].mid != -1) {
            visit[data[i].mid] = true;
            Union(data[i].mid, data[i].id);
        }
        for(int j = 0; j < k; j++) {
            scanf("%d", &data[i].cid[j]);
            visit[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        scanf("%d %d", &data[i].num, &data[i].area);
    }
    for(int i = 0; i < n; i++) {
        int id = find(data[i].id);
        ans[id].id = id;
        ans[id].num += data[i].num;
        ans[id].area += data[i].area;
        ans[id].flag = true;
    }
    for(int i = 0; i < 10000; i++) {
        if(visit[i])
            ans[find(i)].people++;
        if(ans[i].flag)
            cnt++;
    }
    for(int i = 0; i < 10000; i++) {
        if(ans[i].flag) {
            ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
            ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
        }
    }
    sort(ans, ans + 10000, cmp1);
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

struct DATA {

int id, fid, mid, num, area;

int cid[10];

}data[1005];

struct node {

int id, people;

double num, area;

bool flag = false;

}ans[10000];

int father[10000];

bool visit[10000];

int find(int x) {

while(x != father[x])

x = father[x];

return x;

}

void Union(int a, int b) {

int faA = find(a);

int faB = find(b);

if(faA > faB)

father[faA] = faB;

else if(faA < faB)

father[faB] = faA;

}

int cmp1(node a, node b) {

if(a.area != b.area)

return a.area > b.area;

else

return a.id < b.id;

}

int main() {

int n, k, cnt = 0;

scanf("%d", &n);

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

father[i] = i;

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

scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);

visit[data[i].id] = true;

if(data[i].fid != -1) {

visit[data[i].fid] = true;

Union(data[i].fid, data[i].id);

}

if(data[i].mid != -1) {

visit[data[i].mid] = true;

Union(data[i].mid, data[i].id);

}

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

scanf("%d", &data[i].cid[j]);

visit[data[i].cid[j]] = true;

Union(data[i].cid[j], data[i].id);

}

scanf("%d %d", &data[i].num, &data[i].area);

}

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

int id = find(data[i].id);

ans[id].id = id;

ans[id].num += data[i].num;

ans[id].area += data[i].area;

ans[id].flag = true;

}

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

if(visit[i])

ans[find(i)].people++;

if(ans[i].flag)

cnt++;

}

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

if(ans[i].flag) {

ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);

ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);

}

sort(ans, ans + 10000, cmp1);

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

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

printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);

return 0;

}

L2-009. 抢红包-PAT团体程序设计天梯赛GPLT

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（<= 104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

K N1 P1 … NK PK

其中K（0 <= K <= 20）是发出去的红包个数，Ni是抢到红包的人的编号，Pi（> 0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10
输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

分析：用结构体存储下每一个结点的id、收入、收到红包的总数，然后进行排序后输出

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int id, total, getnum;
};
bool cmp1(node a, node b) {
    if(a.total != b.total)
        return a.total > b.total;
    else if(a.getnum != b.getnum)
        return a.getnum > b.getnum;
    else
        return a.id < b.id;
}
int main() {
    int n, k, a, b;
    scanf("%d", &n);
    vector<node> v(n + 1);
    for(int i = 1; i <= n; i++) {
        v[i].id = i;
        scanf("%d", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d %d", &a, &b);
            v[a].total += b;
            v[a].getnum++;
            v[i].total -= b;
        }
    }
    sort(v.begin()+1, v.end(), cmp1);
    for(int i = 1; i <= n; i++) {
        double temp = (double)(v[i].total * 1.0 / 100);
        printf("%d %.2f\n", v[i].id, temp);
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int id, total, getnum;

};

bool cmp1(node a, node b) {

if(a.total != b.total)

return a.total > b.total;

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

return a.getnum > b.getnum;

else

return a.id < b.id;

}

int main() {

int n, k, a, b;

scanf("%d", &n);

vector<node> v(n + 1);

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

v[i].id = i;

scanf("%d", &k);

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

scanf("%d %d", &a, &b);

v[a].total += b;

v[a].getnum++;

v[i].total -= b;

}

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

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

double temp = (double)(v[i].total * 1.0 / 100);

printf("%d %.2f\n", v[i].id, temp);

}

return 0;

}

L2-010. 排座位-PAT团体程序设计天梯赛GPLT（并查集）

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（<= 100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：“宾客1 宾客2 关系”，其中“关系”为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出“No problem”；如果他们之间并不是朋友，但也不敌对，则输出“OK”；如果他们之间有敌对，然而也有共同的朋友，则输出“OK but…”；如果他们之间只有敌对关系，则输出“No way”。

输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but…
No way

分析：朋友之间的关系用并查集解决，敌人之间的关系用enemy[a][b] = enemy[b][a] = 1解决，因为朋友之间的朋友也是朋友，是传递关系，而敌人的敌人不一定是敌人，所以只需要用一个二维数组即可标记。

#include <cstdio>
#include <vector>
using namespace std;
vector<int> fri;
int enemy[101][101];
int findfri(int x) {
    while(x != fri[x])
        x = fri[x];
    return x;
}
void Union(int a, int b) {
    int fria = findfri(a);
    int frib = findfri(b);
    if(fria != frib)
        fri[fria] = frib;
}
int main() {
    int n, m, k, a, b, c;
    scanf("%d %d %d", &n, &m, &k);
    fri.resize(n + 1);
    for(int i = 1; i <= n; i++)
        fri[i] = i;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if(c == 1)
            Union(a, b);
        else {
            enemy[a][b] = 1;
            enemy[b][a] = 1;
        }
    }
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &a, &b);
        if(findfri(a) == findfri(b) && enemy[a][b] == 0)
            printf("No problem\n");
        else if(findfri(a) != findfri(b) && enemy[a][b] == 0)
            printf("OK\n");
        else if(findfri(a) == findfri(b) && enemy[a][b] == 1)
            printf("OK but...\n");
        else if(enemy[a][b] == 1)
            printf("No way\n");
    }
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<int> fri;

int enemy[101][101];

int findfri(int x) {

while(x != fri[x])

x = fri[x];

return x;

}

void Union(int a, int b) {

int fria = findfri(a);

int frib = findfri(b);

if(fria != frib)

fri[fria] = frib;

}

int main() {

int n, m, k, a, b, c;

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

fri.resize(n + 1);

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

fri[i] = i;

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

scanf("%d %d %d", &a, &b, &c);

if(c == 1)

Union(a, b);

else {

enemy[a][b] = 1;

enemy[b][a] = 1;

}

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

scanf("%d %d", &a, &b);

if(findfri(a) == findfri(b) && enemy[a][b] == 0)

printf("No problem\n");

else if(findfri(a) != findfri(b) && enemy[a][b] == 0)

printf("OK\n");

else if(findfri(a) == findfri(b) && enemy[a][b] == 1)

printf("OK but...\n");

else if(enemy[a][b] == 1)

printf("No way\n");

}

return 0;

}