一、algorithm
1、sort
Input：每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output：对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input：
5 3 3 -35 92 213 -644
Sample Output：
213 92 3
代码：
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; bool cmp(int a,int b){ return a>b; } int main(){ int num1,num2; while(cin>>num1>>num2){ int a[100]; for(int i=0;i<num1;i++){ scanf("%d",&a[i]); } sort(a,a+num1,cmp); for(int i=0;i<num2;i++){ cout<<a[i]<<" "; } cout<<endl; } system("pause"); return 0; }
问题2：
Input：The first line is an integer T which indicates the case number.
And as for each case, the first line is an integer n, which is the number of problems.
Then there are n lines followed, with a string and an integer in each line, in the i-th line, the string means the color of ballon for the i-th problem, and the integer means the ballon numbers.
It is guaranteed that:
T is about 100.
1≤n≤10.
1≤ string length ≤10.
1≤ bolloon numbers ≤83.(there are 83 teams :p)
For any two problems, their corresponding colors are different.
For any two kinds of balloons, their numbers are different.
Output：For each case, you need to output a single line.
There should be n strings in the line representing the solving order you choose.
Please make sure that there is only a blank between every two strings, and there is no extra blank.
Sample Input：
3 3 red 1 green 2 yellow 3 1 blue 83 2 red 2 white 1
Sample Output：
yellow green red blue red white
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<string> using namespace std; struct ss{ string col; int val; }num[555]; bool cmp(ss a,ss b){ //return a.val>b.val; if(a.val == b.val){ return a.col>b.col; }else{ return a.val>b.val; } } int main(){ int t; cin>>t; getchar(); while(t--){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>num[i].col; cin>>num[i].val; } sort(num,num+n,cmp); for(int i=0;i<n-1;i++){ cout<<num[i].col<<" "; } cout<<num[n-1].col<<endl; } system("pause"); return 0; }
问题3：插入排序
代码：
#include <cstdio> #include <iostream> using namespace std; int main(){ int temp[100]; for(int i=1;i<=10;i++){ cin>>temp[i]; } for(int i=2;i<=10;i++){ int t = temp[i]; int j = i; while(j>1&&t>temp[j-1]){ temp[j] = temp[j-1]; j--; } temp[j] = t; } for(int i=1;i<=10;i++){ cout<<temp[i]<<" "; } cout<<endl; return 0; }
2、二分（有序序列）
eg:{1,2,2,3,3,3,5,5,5,5}
1
5 3
1 4 6 8 10
0 5
6 10
7 100000
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> using namespace std; int main(){ int t; scanf("%d",&t); for(int j=1;j<=t;j++){ printf("Case %d:\n",j); int n,m; scanf("%d%d",&n,&m); int temp[100010]; for(int i=0;i<n;i++){ scanf("%d",&temp[i]); } while(m--){ int q1,q2; scanf("%d%d",&q1,&q2); int begin = (int)(lower_bound(temp,temp+n,q1)-temp); int end = (int)(upper_bound(temp,temp+n,q2)-temp); printf("%d\n",end-begin); } } return 0; }
3、归并排序与逆序对个数
6 4 11 8Sample Output
1 2 3 5 6 4 1 2 3 4 5 6 7 9 8 11 10
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int main(){ int n,m; while(cin>>n>>m){ int a[2000]; for(int i=0;i<n;i++){ a[i] = i+1; } int p=0; do{ p++; if(p==m){ for(int i=0;i<n-1;i++){ cout<<a[i]<<" "; } cout<<a[n-1]<<endl; break; } }while(next_permutation(a,a+n)); } system("pause"); return 0; }
二、stack
问题1：
Input：The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single line with several words. There will be at most 1000 characters in a line.
Output：For each test case, you should output the text which is processed.
Sample Input：
3 olleh !dlrow m‘I morf .udh I ekil .mca
Sample Output：
hello world! I‘m from hdu. I like acm.
代码：
#include<iostream> #include<algorithm> #include<stack> #include<string> #include<cstdio> using namespace std; int main(){ string s; int t; cin>>t; getchar(); while(t--){ getline(cin,s); int len = (int)s.size(); stack<char>st; for(int i =0;i<len;i++){ if(s[i] != ‘ ‘){ st.push(s[i]); } if(s[i] == ‘ ‘||i == len-1){ while(!st.empty()){ printf("%c",st.top());//获得栈顶元素 st.pop();//弹出栈顶元素 } if(s[i] == ‘ ‘){ cout<<" "; } } } cout<<endl; } system("pause"); return 0; }
问题2：
Input：测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
Output：对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
Sample Input：
1 + 2 4 + 2 * 5 - 7 / 11 0
Sample Output：
3.00 13.36
代码：
#include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; //cout<<"AAAA"<<endl; struct node{ double num; char op; bool flag; }; stack<node> s; queue<node> q; map<char,int> op; void change(string str); double cal(); string str; int main(){ op[‘+‘] = op[‘-‘] = 1; op[‘*‘] = op[‘/‘] = 2; while(getline(cin,str),str!="0"){ string::iterator it; for(it=str.end();it!=str.begin();it--){ if(*it == ‘ ‘){ str.erase(it); } } while(!s.empty()){ s.pop(); } change(str); printf("%0.2f\n",cal()); } system("pause"); return 0; } void change(string str){//前缀变后缀 node temp; for(int i=0;i<(int)str.size();){ if(str[i]==‘(‘){ temp.flag = false; temp.op = str[i]; s.push(temp); i++; }else if(str[i]==‘)‘){ while(!s.empty()&&s.top().op!=‘(‘){ q.push(s.top()); s.pop(); } s.pop(); i++; }else if(str[i]>=‘0‘&&str[i]<=‘9‘){ temp.flag = true; temp.num = str[i] - ‘0‘; i++; while(i<(int)str.size()&&str[i]>=‘0‘&&str[i]<=‘9‘){ temp.num = temp.num*10+(str[i]-‘0‘); i++; } q.push(temp); }else{ temp.flag = false; while(!s.empty()&&op[str[i]]<=op[s.top().op]){ q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp); i++; } } while(!s.empty()){ q.push(s.top()); s.pop(); } } double cal(){//计算后缀表达式:1 1 + double temp1,temp2; node cur,temp; while(!q.empty()){ cur = q.front(); q.pop(); if(cur.flag==true){ s.push(cur); }else{ temp2 = s.top().num; s.pop(); temp1 = s.top().num; s.pop(); temp.flag = true; if(cur.op == ‘+‘){ temp.num = temp1+temp2; }else if(cur.op == ‘-‘){ temp.num = temp1-temp2; }else if(cur.op == ‘*‘){ temp.num = temp1*temp2; }else{ temp.num = temp1/temp2; } s.push(temp); } } return s.top().num; }
三、queue
问题：
Input:The input contains multiple test cases.
The first line has one integer,represent the number oftest cases.
And the input of each subproblem are described above.
Output:For each command "OUT", you should output a integer depend on the word is "FIFO" or "FILO", or a word "None" if you don‘t have any integer.
Sample Input:
4 4 FIFO IN 1 IN 2 OUT OUT 4 FILO IN 1 IN 2 OUT OUT 5 FIFO IN 1 IN 2 OUT OUT OUT 5 FILO IN 1 IN 2 OUT IN 3 OUT
Sample Output:
1 2 2 1 1 2 None 2 3
代码：
#include<iostream> #include<algorithm> #include<queue> #include<stack> #include<string> #include<cstdio> using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; string s1,s2; cin>>s1; if(s1 == "FIFO"){ queue<int> qu; while(n--){ cin>>s2; if(s2 == "IN"){ int num; cin>>num; qu.push(num); }else{ if(qu.empty()){ cout<<"None"<<endl; }else{ cout<<qu.front()<<endl; qu.pop(); } } } }else{ stack<int> st; while(n--){ cin>>s2; if(s2 == "IN"){ int num; cin>>num; st.push(num); }else{ if(st.empty()){ cout<<"None"<<endl; }else{ cout<<st.top()<<endl; st.pop(); } } } } } system("pause"); return 0; }
四、set（内部自动有序、不含重复）
问题：
Input输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。
Output对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。
Sample Input
3 Alice Bob Smith John Alice Smith 5 a c c d d e b e a d 0
Sample Output
Yes No
代码：
#include<iostream> #include<algorithm> #include<set> #include<string> #include<cstdio> using namespace std; int main(){ int t; while(cin>>t){ if(t == 0){ break; } set<string> st1,st2; string s1,s2; while(t--){ cin>>s1>>s2; st1.insert(s1); st1.insert(s2); st2.insert(s2); } if(st1.size()-st2.size() != 1){ cout<<"No"<<endl; }else{ cout<<"Yes"<<endl; } } system("pause"); return 0; }
五、迭代器
问题：
Input每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束，不做处理。
Output针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.
Sample Input
3 3 1 2 3 1 4 7 3 7 2 5 8 2 3 4 5 6 7 8 0 0
Sample Output
2 3 NULL
代码：
#include<iostream> #include<algorithm> #include<set> #include<string> #include<cstdio> using namespace std; int main(){ int num1,num2; while(cin>>num1>>num2){ if(num1 == num2&&num1 == 0){ break; } int num; set<int> st; for(int i=0;i<num1;i++){ cin>>num; st.insert(num); } for(int i=0;i<num2;i++){ cin>>num; if(st.find(num) != st.end()){ st.erase(num); } } if(st.size() == 0){ cout<<"NULL"<<endl; continue; } set<int>::iterator it; for(it=st.begin();it!=st.end();it++){ cout<<*it<<" "; } cout<<endl; } system("pause"); return 0; }
六、map(键值对)
问题：
InputOne line contians a number n ( n<=10000),stands for the number of shops.
Then n lines ,each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.)stands for the name of the shop.
Then a line contians a number m (1<=m<=50),stands for the days .
Then m parts , every parts contians n lines , each line contians a number s and a string p ,stands for this day ,the shop p ‘s price has increased s.
OutputContains m lines ,In the ith line print a number of the shop "memory" ‘s rank after the ith day. We define the rank as :If there are t shops‘ price is higher than the "memory" , than its rank is t+1.Sample Input
3 memory kfc wind 2 49 memory 49 kfc 48 wind 80 kfc 85 wind 83 memory
Sample Output
1 2
代码：
#include<iostream> #include<algorithm> #include<map> #include<string> #include<cstdio> using namespace std; int main(){ int t; while(cin>>t){ for(int i=0;i<t;i++){ string s; cin>>s; } int n; cin>>n; map<string,int> shop; while(n--){ for(int i=0;i<t;i++){ string name; int price; cin>>price; cin>>name; shop[name]+=price; } map<string,int>::iterator it; int mas = 1; for(it=shop.begin();it!=shop.end();it++){ if(it->second>shop["memory"]){ mas++; } } cout<<mas<<endl; } } system("pause"); return 0; }
七、priority_queue(优先队列)
问题：
Input输入数据包含多组测试，请处理到文件结束。
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件：
1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)
Output对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。
Sample Input
7 IN 1 1 IN 1 2 OUT 1 OUT 2 IN 2 1 OUT 2 OUT 1 2 IN 1 1 OUT 1
Sample Output
2 EMPTY 3 1 1
代码：
#include<iostream> #include<algorithm> #include<queue> #include<string> #include<cstdio> using namespace std; struct node{ int value,id; bool operator<(const node &b)const{ if(value == b.value){ return id>b.id; }else{ return value<b.value; } } }; int main(){ int t; while(cin>>t){ node pep; priority_queue<node> q[10]; int time = 1; string s; while(t--){ cin>>s; if(s == "IN"){ int a; cin>>a>>pep.value; pep.id = time; time++; q[a-1].push(pep); }else{ int a; cin>>a; if(q[a-1].empty()){ cout<<"EMPTY"<<endl; }else{ cout<<q[a-1].top().id<<endl; q[a-1].pop(); } } } } system("pause"); return 0; }
八、list
问题：
Input本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。
Output共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。
Sample Input
2 20 40
Sample Output
1 7 19 1 19 37
代码1：
#include<iostream> #include<algorithm> #include<queue> #include<string> #include<cstdio> #include<stack> #include<list> #include<cmath> #include<cstring>// #include<cstdlib>// using namespace std; int main(){ int t,n; cin>>t; while(t--){ cin>>n; int k = 2; list<int> blist; list<int>::iterator it; for(int i=1;i<=n;i++){ blist.push_back(i); } while(blist.size()>3){ int num =1; for(it=blist.begin();it!=blist.end();){ if(num++%k == 0){ it = blist.erase(it); }else{ it++; } } if(k == 2){ k = 3; continue; }else{ k = 2; continue; } //k==2?k=3:k=2; } for(it=blist.begin();it!=blist.end();it++){ if(it!=blist.begin()){ cout<<" "; } cout<<*it; } cout<<endl; } system("pause"); return 0; }
代码2：
原文：https://www.cnblogs.com/bijian/p/12373204.html