7-5 一帮一 (15 分)

题目

“一帮一学习小组”是中小学中常见的学习组织方式，老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作，即在得到全班学生的排名后，在当前尚未分组的学生中，将名次最靠前的学生与名次最靠后的异性学生分为一组。

输入格式：
输入第一行给出正偶数N（≤50），即全班学生的人数。此后N行，按照名次从高到低的顺序给出每个学生的性别（0代表女生，1代表男生）和姓名（不超过8个英文字母的非空字符串），其间以1个空格分隔。这里保证本班男女比例是1:1，并且没有并列名次。

输出格式：
每行输出一组两个学生的姓名，其间以1个空格分隔。名次高的学生在前，名次低的学生在后。小组的输出顺序按照前面学生的名次从高到低排列。

输入样例：

8
0 Amy
1 Tom
1 Bill
0 Cindy
0 Maya
1 John
1 Jack
0 Linda

输出样例：

Amy Jack
Tom Linda
Bill Maya
Cindy John

思路

知识点

• pair<数据类型,数据类型>的使用

代码

#include<stack>
#include<iostream>
using namespace std;
int main() {int n;cin >> n;pair<int, string> stu[50];for(int i=0; i<n; i++) cin >> stu[i].first >> stu[i].second;int j = n-1, k = n-1;for(int i=0; i<n/2; i++) {cout << stu[i].second;if(stu[i].first==0) {while(stu[j].first==0) j--;cout << " " << stu[j].second << endl;j--;} else {while(stu[k].first==1) k--;cout << " " << stu[k].second << endl;k--;}}
}

7-6 考试座位号 (15 分)

题目

每个 PAT 考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。

输入格式：
输入第一行给出一个正整数 N（≤1000），随后 N 行，每行给出一个考生的信息：准考证号 试机座位号 考试座位号。其中准考证号由 16 位数字组成，座位从 1 到 N 编号。输入保证每个人的准考证号都不同，并且任何时候都不会把两个人分配到同一个座位上。

考生信息之后，给出一个正整数 M（≤N），随后一行中给出 M 个待查询的试机座位号码，以空格分隔。

输出格式：
对应每个需要查询的试机座位号码，在一行中输出对应考生的准考证号和考试座位号码，中间用 1 个空格分隔。

输入样例：

4
3310120150912233 2 4
3310120150912119 4 1
3310120150912126 1 3
3310120150912002 3 2
2
3 4

输出样例：

3310120150912002 2
3310120150912119 1

思路

代码

#include<iostream>
using namespace std;
int main() {int n;cin >> n;string a[1001][2];for(int i=0; i<n; i++) {string s;int x;cin >> s >> x;a[x][0] = s;cin >> a[x][1];}cin >> n;for(int i=0; i<n; i++) {int x;cin >> x;cout << a[x][0] << " " << a[x][1] << endl;}return 0;
}

7-7 删除重复字符 (20 分)

题目

本题要求编写程序，将给定字符串去掉重复的字符后，按照字符ASCII码顺序从小到大排序后输出。

输入格式：
输入是一个以回车结束的非空字符串（少于80个字符）。

输出格式：
输出去重排序后的结果字符串。

输入样例：

ad2f3adjfeainzzzv

输出样例：

23adefijnvz

目标

去重+排序

思路

• 第一种：以数据作为数组下标后按顺序输出
• 第二种：使用set容器完成去重＋排序的操作

代码

思路一代码：

#include<bits/stdc++.h>
using namespace std;
int main() {string s;getline(cin, s);sort(s.begin(), s.end());int a[256] = {0};for(char x:s) {if(a[x]==0) {cout << x;a[x] = 1;}}return 0;
}

思路二代码：

#include <bits/stdc++.h>
using namespace std;
int main(){set<char> s;char c;string str;getline(cin,str);for(int i=0;i<str.length();i++){s.insert(str[i]);}for(auto ss:s){cout<<ss;}
}

7-8 最长的括号子串 (20 分)

题目

给出一个长度为 n 的，仅包含字符 ‘(’ 和 ‘)’ 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 “(()” 来说，最长的格式正确的子串是 “()” ，长度为 2 . 例2：对于字符串 “)()())” , 来说, 最长的格式正确的子串是 “()()” ，长度为 4 .
字符串长度：0≤n≤5∗10 5
输入格式:
只由’(’ 和 ‘)’ 组成的字符串。
输出格式:
输出最长的合法括号子串的长度。
输入样例:
在这里给出一组输入。例如：

)()())

输出样例:
在这里给出相应的输出。例如：

4

技巧

下标入栈 而不是 符号入栈。（详见代码）

代码

#include<bits/stdc++.h>
using namespace std;
int main() {string s;cin >> s;stack<int> st;int res = 0;for(int i=0; s[i]; i++) {if(s[i]==')' && !st.empty() && s[st.top()]=='(') {st.pop();if(st.empty()) res = i+1;else res = max(res, i-st.top());} else st.push(i);}cout << res;return 0;
}

7-9 家庭房产 (25 分)

题目

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

输入格式：
输入第一行给出一个正整数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

知识点

• 并查集
  并查集代码模板：

int pre[10000];
int root(int x) {while(pre[x]!=x) x = pre[x];return x;
}
void un(int x, int y) {int rootx = root(x);int rooty = root(y);if(rootx<rooty) pre[rooty] = rootx;else pre[rootx] = rooty;
}

• 结构体排序

思路

在读入数据时使用 ==并查集 ==不断合并家庭。然后以 人均面积+编号排序 排序，最后输出。

代码

#include <bits/stdc++.h>
using namespace std;
struct node{int id = -1;int num;double house = 0;double area = 0;
};
int pre[10000];
int root(int x){while(pre[x]!=x) x = pre[x];return x;
}
void un(int x,int y){int rootx = root(x);int rooty = root(y);if(rootx<rooty) pre[rooty] = rootx;else pre[rootx] = rooty;
}
bool cmp(node x,node y){if(x.area/x.num == y.area/y.num) return x.id<y.id;else return x.area/x.num > y.area/y.num;
}
int main(){for(int i=0;i<10000;i++) pre[i] = i;node arr[10000];bool exist[10000] = {0};//记录出现过的编号 int n;cin>>n;for(int i=0;i<n;i++){int id,fa,ma;cin>>id>>fa>>ma;arr[id].id = id;exist[id] = 1;if(fa!=-1){exist[fa] = 1;un(id,fa);//fa存在，则与该id对应的人是一个家庭的，使用un（）合并 }if(ma!=-1){exist[ma] = 1;un(id,ma);//同理，合并ma }int k,x;cin>>k;while(k--){cin>>x;un(id,x);//每个儿子和该id对应的人同属一个家庭，使用un()合并exist[x] = 1; }cin>>arr[id].house>>arr[id].area;}node tmp[10000];for(int i=0;i<10000;i++){if(exist[i]){//该编号存在int f = root(i);//该编号所在家庭的最小编号//每个家庭对应着一个根节点，因此可通过该根节点统计各个家庭的人数tmp[f].id = f;tmp[f].num++;if(arr[i].id!=-1)//该编号对应的人有房产{tmp[f].house+=arr[i].house;tmp[f].area+=arr[i].area;} }}node res[10000];int i = 0;for(int j=0;j<10000;j++){//把每一个家庭复制到res if(tmp[j].id!=-1) res[i++] = tmp[j];} sort(res,res+i,cmp);cout<<i<<'\n';for(int j=0;j<i;j++){printf("%04d %d %.3lf %.3lf\n",res[j].id,res[j].num,res[j].house/res[j].num,res[j].area/res[j].num);}}

7-10 直直直径 (25 分)

题目

Keven现在有一棵树，现在Keven想知道在这颗树上任取两点，他们的距离的最大值是多少，Keven不会做这个题目，于是请教聪明的你，如果你帮助他解决这个问题，他将会让你的排名上升。

树中两点之间的距离定义为连接两点的路径边权之和。并且每条路径经过的次数不能超过1次。

输入格式:
第一行给出一个数字N，表示树的节点个数。（树的节点为1-N）

接下来N-1行，每行给出三个数字U，V，W，表示点U与点V之间有一条权值为W的路径。

（N<200000，W<100000000）

输出格式:
在一行中输出树上任意两点距离的最大值。

输入样例:
在这里给出一组输入。例如：

4
1 2 5
1 3 6
1 4 7

输出样例:
在这里给出相应的输出。例如：

13

###案例解释

第三个点到第四个点的距离最大，最大值为13。

知识点

• 深度优先搜索（dfs）

void dfs(int t, bool vis[], long long len) {if(vis[t]==1) return;vis[t] = 1;if(len>res) res = len;for(auto x:a[t])if(!vis[x.first]) dfs(x.first, vis, len+x.second);
}

• stl中pair的用法

思路

将它看成图，深搜每一条路径，过程中刷新最大值res

代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > a[200000];
long long res = 0;
void dfs(int t,bool vis[],long long len){if(vis[t] == 1) return ;vis[t] = 1;if(res<len) res = len;for(auto x:a[t]){if(!vis[x.first]) dfs(x.first,vis,len+x.second);}
}
int main(){int n;cin>>n;for(int i=1;i<n;i++){int x,y,w;cin>>x>>y>>w;a[x].push_back({y,w});//注意pair可以这样操作 a[y].push_back({x,w});}for(int i=1;i<n;i++)//从每个点开始遍历，不断刷新最大len{if(a[i].size() == 1){//不加这个会有一个点会超时 bool vis[200000] = {0};dfs(i,vis,0);}} cout<<res;
}

7-11 储水问题 (25 分)

题目

给定一系列非负整数，将这些数据看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：0≤n≤10
6
，数组中每个值满足 0 <val≤10
9

输入格式:
第一行是n值，第二行是n个非负数

输出格式:
输出能接的雨水单位数

输入样例:

6
3 1 2 5 2 4

输出样例:

5

说明：柱子高度分别为3,1,2,5,2,4, 如图所示。在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 。

思路

1. left，right先定位到左边、右边的第一个围栏（能把水围住那栏）下标。
2. x=left的栏高, y=right的栏高
3. 如果 本次 x<y，那就从left+1（下标）开始，顺序计算接下来的每一栏比x低多少并累计，直到某栏高
   于x。期间left++
   如果 本次 x>=y, 那就从right-1（下标）开始，顺序计算接下来的每一栏比y低多少并累计，直到某栏高
   于y。期间right–
4. 回到第二点，直到left>=right

参考：经典算法–最大存水量问题

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main() {int n;cin >> n;for(int i=0; i<n; i++) cin >> a[i];int left, right;
//	因为左围栏左边和右围栏右边不能储水，所以先定位left和right到左右围栏 //找左边围栏下标for(left=0; left<n-1 && a[left]<=a[left+1]; left++);//找右边围栏下标for(right=n-1; right>0 && a[right]<=a[right-1]; right--);long long res = 0;int x, y;while(1){if(left>=right) break;x = a[left];y = a[right];if(x<y)//一直到遇到比x大的位置时固定left，期间x-a[left]即为该位置能接的雨水单位数 while(left<right && a[++left]<=x) res += x-a[left];		else//一直到遇到比y大的位置时固定right，期间y-a[right]即为该位置能接的雨水单位数 while(left<right && a[--right]<=y) res += y-a[right];}cout << res;
}

7-12 德才论 (25 分)

题目

宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”

现给出一批考生的德才分数，请根据司马光的理论给出录取排名。

输入格式：
输入第一行给出 3 个正整数，分别为：N（≤10
5
），即考生总数；L（≥60），为录取最低分数线，即德分和才分均不低于 L 的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于 H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。

随后 N 行，每行给出一位考生的信息，包括：准考证号、德分、才分，其中准考证号为 8 位整数，德才分为区间 [0, 100] 内的整数。数字间以空格分隔。

输出格式：
输出第一行首先给出达到最低分数线的考生人数 M，随后 M 行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。

输入样例：

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

输出样例：

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

思路

按照题目要求进行排序输出就行，要细心

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct person {string num;int de;int cai;
};
bool cmp(person x, person y) {if(x.de+x.cai != y.de+y.cai) return x.de+x.cai > y.de+y.cai;else if(x.de != y.de) return x.de > y.de;else return x.num < y.num;
}
void output(vector<person> x) {for(auto t:x)cout << t.num << " " << t.de << " " << t.cai << endl;
}
int main() {int n, l, h;cin >> n >> l >> h;string num;int x, y;vector <person> c1, c2, c3, c4;for(int i=0; i<n; i++) {cin >> num >> x >> y;if(x>=h && y>=h) c1.push_back({num, x, y});else if(x>=h && y>=l) c2.push_back({num, x, y});else if(x>=l && y>=l && x>=y) c3.push_back({num, x, y});else if(x>=l && y>=l) c4.push_back({num, x, y});}sort(c1.begin(), c1.end(), cmp);sort(c2.begin(), c2.end(), cmp);sort(c3.begin(), c3.end(), cmp);sort(c4.begin(), c4.end(), cmp);cout << c1.size()+c2.size()+c3.size()+c4.size() << endl;output(c1);output(c2);output(c3);output(c4);return 0;
}

7-13 银行排队问题之单窗口“夹塞”版 (25 分)

题目

排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友，并且愿意替朋友办理事务的话，那么第i位顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。在这种情况下，顾客的等待时间就可能被影响。假设所有人到达银行时，若没有空窗口，都会请求排在最前面的朋友帮忙（包括正在窗口接受服务的朋友）；当有不止一位朋友请求某位顾客帮忙时，该顾客会根据自己朋友请求的顺序来依次处理事务。试编写程序模拟这种现象，并计算顾客的平均等待时间。

输入格式:
输入的第一行是两个整数：1≤N≤10000，为顾客总数；0≤M≤100，为彼此不相交的朋友圈子个数。若M非0，则此后M行，每行先给出正整数2≤L≤100，代表该圈子里朋友的总数，随后给出该朋友圈里的L位朋友的名字。名字由3个大写英文字母组成，名字间用1个空格分隔。最后N行给出N位顾客的姓名、到达时间T和事务处理时间P（以分钟为单位），之间用1个空格分隔。简单起见，这里假设顾客信息是按照到达时间先后顺序给出的（有并列时间的按照给出顺序排队），并且假设每个事务最多占用窗口服务60分钟（如果超过则按60分钟计算）。

输出格式:
按顾客接受服务的顺序输出顾客名字，每个名字占1行。最后一行输出所有顾客的平均等待时间，保留到小数点后1位。

输入样例:

6 2
3 ANN BOB JOE
2 JIM ZOE
JIM 0 20
BOB 0 15
ANN 0 30
AMY 0 2
ZOE 1 61
JOE 3 10

输出样例:

JIM
ZOE
BOB
ANN
JOE
AMY
75.2

ps：题目太长了，暂时还没看，先放着

代码

#include<bits/stdc++.h>
using namespace std;
map<string, pair<int, int>> cus;//姓名:<到达时间，时长>
map<string, int> fri;//姓名：圈子
string a[10000];
int main() {int n, m;cin >> n >> m;for(int i=0; i<m; i++) {int k;cin >> k;while(k--) {string s;cin >> s;fri[s] = i;}}for(int i=0; i<n; i++) {int x, y;cin >> a[i] >> x >> y;cus[a[i]] = {x, min(60, y)};}int now = 0;int sum = 0;for(int i=0; i<n; i++) {auto tmp = cus[a[i]];if(tmp.first==-1)//已服务continue;cout << a[i] << endl;sum += max(0, now-tmp.first);now = max(now, tmp.first) + tmp.second;
//cout << "sum: " << sum << endl;for(int j=i+1; j<n; j++) {
//cout << "jia: " << a[j] << endl;auto tmp = cus[a[j]];auto x = fri.find(a[i]), y = fri.find(a[j]);if(x!=fri.end() && y!=fri.end())if(tmp.first!=-1 && x->second==y->second && tmp.first<=now) {//加塞cout << a[j] << endl;cus[a[j]].first = -1;sum += (now-tmp.first);now += tmp.second;
//cout << "sum: " << sum << endl;}}}printf("%.1f", 1.0*sum/n);return 0;
}