排序
徐仓仓 Lv3

📅time:8.19 -

🍔题目:

1012 25 The Best Rank
1016 25 Phone Bills 模拟题 属于是遇到直接不想做的题
1026 30 Table Tennis 大模拟 听说不考,算了
1028 25 List Sorting 结构体排序 世界上最简单的题目
1055 25 The World’s Richest
1062 25 Talent and Virtue
1075 25 PAT Judge
1083
1095
1098
1101
1113
1137
1141
1153

chronological order

alphabetical order

附录

1012 The Best Rank

史上最笨的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000000;
int N, M;
vector<int>a,c,m,e;
struct node {
int s;
int A, C, M, E;
};
node* stu[maxn];
bool cmp(int a, int b) {
return a > b;
}
int main() {
cin >> N >> M;
int sno;
for (int i = 0; i < N; i++) {
node* p = new node();
scanf("%d%d%d%d", &p->s, &p->C, &p->M, &p->E);
p->A = (p->C + p->M + p->E) / 3;
a.push_back(p->A);
c.push_back(p->C);
m.push_back(p->M);
e.push_back(p->E);
stu[p->s] = p;
}
sort(a.begin(), a.end(), cmp);
sort(c.begin(), c.end(), cmp);
sort(m.begin(), m.end(), cmp);
sort(e.begin(), e.end(), cmp);
for (int i = 0; i < M; i++) {
cin >> sno;
if (stu[sno] == NULL) {
cout << "N/A\n";
continue;
}
int rank = 2001; char rely = 'A';
for (int j = 0; j < a.size(); j++) {
if (stu[sno]->A == a[j]) {
rank = j;
}
}
for (int j = 0; j < c.size(); j++) {
if (stu[sno]->C == c[j]) {
if (rank > j) {
rank = j;
rely = 'C';
}
}
}
for (int j = 0; j < m.size(); j++) {
if (stu[sno]->M == m[j]) {
if (rank > j) {
rank = j;
rely = 'M';
}
}
}
for (int j = 0; j < e.size(); j++) {
if (stu[sno]->E == e[j]) {
if (rank > j) {
rank = j;
rely = 'E';
}
}
}
cout << rank + 1 << " " << rely << "\n";
}
}

1016 Phone Bills

属于是遇到直接不想做的题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int N, rate[25];
struct node {
string name;
int status, mon, day, hour, minute, time;
};
bool cmp(node* a, node* b) {
if (a->name != b->name)
return a->name < b->name;
return a->time < b->time;
}
vector<node*>bill;
map<string, int>id;
double money(node* a) {//计算每个电话从1号00:00:00的钱
double total = rate[a->hour] * a->minute + rate[24] * 60 * a->day;
for (int i = 0; i < a->hour; i++) {
total += rate[i] * 60;
}
return total/100.0;
}
int main() {
for (int i = 0; i < 24; i++) {
cin >> rate[i];
rate[24] += rate[i];
}
cin >> N;
string name, act;
int M, d, H, m;
int peoplenum = 0;
for (int i = 0; i < N; i++) {
cin >> name;
scanf("%d:%d:%d:%d", &M, &d, &H, &m);
cin >> act;
if (id.count(name) == 0) id[name] = peoplenum++;
node* p = new node();
p->name = name;
p->mon = M;
p->day = d;
p->hour = H;
p->minute = m;
p->time = d * 24 * 60 + H * 60 + m;
if (act == "on-line") p->status = 1;//接
else p->status = 0;//挂
bill.push_back(p);
}
map<string, vector<node*>>cost;
sort(bill.begin(), bill.end(), cmp);
for (int i = 0; i < bill.size()-1; i++) {
if (bill[i]->name == bill[i + 1]->name && bill[i]->status == 1 && bill[i + 1]->status == 0) {
cost[bill[i]->name].push_back(bill[i]);
cost[bill[i]->name].push_back(bill[i + 1]);
}
}
for (auto it : cost) {
vector<node*>temp = it.second;
double total = 0;
printf("%s %02d\n", it.first.c_str(), it.second[0]->mon);
for (int i = 0; i < temp.size()-1;i++) {
printf("%02d:%02d:%02d %02d:%02d:%02d ", temp[i]->day, temp[i]->hour, temp[i]->minute, temp[i+1]->day, temp[i+1]->hour, temp[i+1]->minute);
cout << temp[i + 1]->time - temp[i]->time<<" ";
double m = money(temp[i + 1]) - money(temp[i]);
total += m;
printf("\$%.02f\n", m);
i++;
}
printf("Total amount: ");
printf("\$%.02f\n", total);
}
}

1026 Table Tennis

1028 List Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N, C;
struct node {
int sno, grade;
string name;
};
vector<node*>stu;
bool cmp(node* a, node* b) {
if (C == 1) return a->sno < b->sno;
else if (C == 2&& a->name != b->name) {
return a->name < b->name;
}
else if (C == 3&& a->grade != b->grade) {
return a->grade > b->grade;
}
return a->sno < b->sno;
}
int main() {
cin >> N >> C;
for (int i = 0; i < N; i++) {
node* p = new node();
cin >> p->sno >> p->name >> p->grade;
stu.push_back(p);
}
sort(stu.begin(), stu.end(), cmp);
for (auto it : stu) {
printf("%06d %s %d\n", it->sno, it->name.c_str(), it->grade);
}
}

1055 The World’s Richest

应该对所有人进行财富排序,每次输入条件后,遍历一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
struct node {
string name;
int age, money;
};
bool cmp(node* a, node* b) {
if (a->money != b->money)
return a->money > b->money;
else if (a->age != b->age)
return a->age < b->age;
return a->name < b->name;
}
vector<node*>G;
vector<node*>temp;
int main() {
cin >> N >> M;
string n;
int a, m;
for (int i = 0; i < N; i++) {
cin >> n;
scanf("%d%d", &a, &m);
node* p = new node();
p->age = a;
p->name = n;
p->money = m;
G.push_back(p);
}
sort(G.begin(), G.end(), cmp);
int num, min, max;
for (int i = 1; i <= M; i++) {
scanf("%d%d%d", &num, &min, &max);
printf("Case #%d:\n", i);
for (int j = 0; j < G.size(); j++) {
if (G[j]->age >= min && G[j]->age<=max) {
temp.push_back(G[j]);
}
if (temp.size() == num) break;
}
if (temp.size() == 0) { printf("None\n"); continue; }
for (int j = 0; j < temp.size(); j++) {
cout << temp[j]->name << " ";
printf("%d %d\n", temp[j]->age, temp[j]->money);
}
temp.clear();
}
}

1062 Talent and Virtue

sort中报错没有参数可能是因为cmp中没有把情况写全,或者排序超出数组范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N,L,H;
struct node {
int sno, virtue, talent;
};
vector<node*>G;
int judge(node* a) {
if (a->virtue >= H && a->talent >= H)return 1;//圣人
if (a->talent<H && a->virtue>=H) return 2;//君子
if (a->virtue >= a->talent) return 3;//愚人
return 4;//小人
}
bool cmp(node* a, node* b) {
int ja = judge(a);
int jb = judge(b);
if (ja!=jb) {
return ja < jb;
}
int totala = a->talent + a->virtue;
int totalb = b->talent + b->virtue;
if (totala != totalb) return totala > totalb;
if (a->virtue != b->virtue) return a->virtue > b->virtue;
return a->sno < b->sno;
}
int main() {
cin >> N >> L >> H;
int id, v, t;
for (int i = 0; i < N; i++) {
scanf("%d %d %d", &id, &v, &t);
if (v >=L && t >= L) {
node* p = new node();
p->sno = id;
p->virtue = v;
p->talent = t;
G.push_back(p);
}
}
cout << G.size() << endl;
sort(G.begin(), G.end(), cmp);
for (auto it : G) {
printf("%08d %d %d\n", it->sno, it->virtue, it->talent);
}
}

1075 PAT Judge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int N, K, M;
struct node {
int sno;
int total = 0;
int score[6] = { -1,-1,-1,-1,-1,-1 };
int perfect = 0;
};
vector<node*>stu;
int problem[6];
map<int, int>index;
bool cmp(node* a, node* b) {
if (a->total != b->total)
return a->total > b->total;
if (a->perfect != b->perfect)
return a->perfect > b->perfect;
return a->sno < b->sno;
}
bool flag[10000];
int main() {
cin >> N >> K >> M;
for (int i = 1; i <= K; i++) {
cin >> problem[i];
}
int sno, pro, grade;
int num = 0;
for (int i = 0; i < M; i++) {
cin >> sno >> pro >> grade;
if (grade != -1) flag[sno] = true;
if (grade == -1) grade = 0;
if (index.count(sno) == 0) {
node* p = new node();
p->score[pro] = grade;
p->sno = sno;
p->total = grade;
stu.push_back(p);
index[sno] = num++;
if (grade == problem[pro]) p->perfect++;
}
else {
int s = stu[index[sno]]->score[pro];
if (s < grade) {
int z = max(s, 0);
stu[index[sno]]->total += grade - z;
stu[index[sno]]->score[pro] = grade;
if (grade == problem[pro]) stu[index[sno]]->perfect++;
}
}
}
sort(stu.begin(), stu.end(), cmp);
int rank = 0, score = 101, same = 1;
for (int i = 0; i < stu.size(); i++) {
if (!flag[stu[i]->sno]) continue;
if (stu[i]->total < score) {
score = stu[i]->total;
rank += same;
same = 1;
}
else same++;
printf("%d %05d %d ", rank, stu[i]->sno,stu[i]->total);
for (int j = 1; j <= K; j++) {
if (stu[i]->score[j] == -1)
cout << "-";
else cout << stu[i]->score[j];
if (j == K) cout << endl;
else cout << " ";
}
}
}
 Comments