STL练习
2058: [STL训练]Who's in the Middle
题目描述
FJ is surveying his herd to find the most average cow.He wants to know how much milk this 'median' cow gives:half of the cows give as much or more than the median; half give as much or less.
Given an odd number of cows N (1 <= N < 10,000) and their milk output (1..1,000,000), find the median amount of milk given such that at least half the cows give the same amount of milk or more and at least half give the same or less.
输入格式
* Line 1: A single integer N
* Lines 2..N+1: Each line contains a single integer that is the milk
output of one cow.
输出格式
* Line 1: A single integer that is the median milk output.
样例输入
复制
5 2 4 1 3 5
样例输出
复制
3
#include<bits/stdc++.h> using namespace std; int main(){ int n,mid; cin>>n; vector<int>d; for(int i=0;i<n;i++){ int m; cin>>m; d.push_back(m); }//数据 sort(d.begin(),d.end());//对容器中的元素从小到大排序 mid=d[n/2]; cout<<mid; return 0; }代码中运用sort排序
从小到大：sort(d.begin(),d.end());
从大到小：sort(d.begin(),d.end(),greater<int>());
2059: [STL训练]sort练习
题目描述
给你n个整数，请按从大到小的顺序输出其中前m大的数
输入格式
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，
第二行包含n个各不相同，且都处于区间[-500000,500000]的整数
输出格式
对每组测试数据按从大到小的顺序输出前m大的数。
样例输入
复制
5 3 3 -35 92 213 -644
样例输出
复制
213 92 3
#include<bits/stdc++.h> using namespace std; int main(){ int n=0; int m=0; cin>>n>>m; vector<int>d; for(int i=0;i<n;i++){ int k=0; cin>>k; d.push_back(k); } sort(d.begin(),d.end(),greater<int>()); for(int j=0;j<m;j++){ cout<<d[j]<<" "; } return 0; }代码中运用sort排序
从小到大：sort(d.begin(),d.end());
从大到小：sort(d.begin(),d.end(),greater<int>());
2060: [STL训练]美国大选
题目描述
美国大选是按各州的投票结果来确定最终的结果的，如果得到超过一半的州的支 持就可以当选，而每个州的投票结果又是由该州选民投票产生的，如果某个州超过一半的选民支持希拉里，则她将赢得该州的支持。现在给出每个州的选民人数，请问希拉里至少需要赢得多少选民的支持才能当选？
输入格式
多组输入数据
每组数据的第一行包括一个整数N（1<=N<=101）,表示美国的州数，N=0表示输入
结束
接下来一行包括N个正整数，分别表示每个州的选民数，每个州的选民数不超过
100
输出格式
对于每组数据输出一行，表示希拉里至少需要赢得支持的选民数
样例输入
复制
3 5 7 5 0
样例输出
复制
6
题意理解：
有多组测试数据，有结束条件（N=0表示输入 结束）需要用while；
当选需要超过一半的州或人（注意数据加一）
sort排序（至少需要赢得支持的选民数）从小到大排
#include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n&&n!=0){ int sum=0; vector<int>d; for(int i=0;i<n;i++){ int m; cin>>m; d.push_back(m); } sort(d.begin(),d.end()); for(int j=0;j<n/2+1;j++){ sum+=d[j]/2+1; } cout<<sum<<endl; } return 0; }2061: [STL训练]周瑜的反间计
输入格式
本题包含多组case。每组case第一行是一个整数N（1<=N<=1000），当N为-1时输入结束且不需要输出。接下来输入N个不同的数字，代表已有文件的编号，编号i的范围是（0<=i<=2^31-1）。然后是一个整数M（1<=M<=100000），接下来的M个数字代表M个询问，询问当前输入编号所代表的文件是否为真实的。
输出格式
对于每一个询问，如果该编号所代表的文件是真是的，输出“YES”，否则
输出“NO”。每组case后有一个空行。
样例输入
复制
3 4 10 6 2 1 4 -1
样例输出
复制
NO YES
题意理解：
有多组测试数据且有结束条件，用while
需要对比输出的数据，使用二分法if(binary_search(d.begin(),d.end(),k2))，将k2和d容器里的数据比较查找
#include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n&&n!=-1){ vector<int>d; for(int i=0;i<n;i++){ int k1; cin>>k1; d.push_back(k1); } sort(d.begin(), d.end()); int m; cin>>m; for(int j=0;j<m;j++){ int k2; cin>>k2; if(binary_search(d.begin(),d.end(),k2)){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } //注意细节 cout<<endl; } return 0; }2062:
[STL训练]第二小整数
题目描述
求n个整数中倒数第二小的数。
每一个整数都独立看成一个数，比如，有三个数分别是1，1，3，那么，第二小
的数就是1。
输入格式
输入包含多组测试数据。
输入的第一行是一个整数C，表示有C测试数据；
每组测试数据的第一行是一个整数n，表示本组测试数据有n个整（2<=n<=10），
接着一行是 n个整数 (每个数均小于100);
输出格式
请为每组测试数据输出第二小的整数，每组输出占一行。
样例输入
复制
2 2 1 2 3 1 1 3
样例输出
复制
2 1
题意理解：
注意第二小，排序问题可以用sort
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; for(int i=0;i<n;i++){ int m; cin>>m; vector<int>d; for(int j=0;j<m;j++){ int k; cin>>k; d.push_back(k); } sort(d.begin(),d.end()); cout<<d[1]<<endl; } }2065: [STL训练]{A} + {B}
题目描述
给你两个集合，要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.
输入格式
每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),
分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.
每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.
输出格式
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,
每个元素之间有一个空格隔开.
样例输入
复制
1 2 1 2 3 1 2 1 1 2
样例输出
复制
1 2 3 1 2
set容器插入数据用insert，set容器自带去重和排序功能。
for(int num:c){
cout<<num<<" ";
}//遍历c中所有数据
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; while(cin>>n>>m){ set<int>a; set<int>b; set<int>c; for(int i=0;i<n;i++){ int k1; cin>>k1; a.insert(k1); } for(int j=0;j<m;j++){ int k2; cin>>k2; b.insert(k2); } c.insert(a.begin(), a.end()); // 插入a的所有元素 c.insert(b.begin(), b.end()); for(int num:c){ cout<<num<<" "; } } return 0; }