车厢重组

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排序。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入文件

输入文件有两行数据，第一行是车厢总数N（不大于1000），第二行是N个不同的数表示初始的车厢顺序。

输出文件

一个数据，是最少的旋转次数。

输入样例

4
4 3 2 1

输出样例

参考代码

[+]

#include <iostream>
using namespace std;

int n,a[10005],ans=0;
int main(){
	cin >> n;	
	for(int i=1;i<=n;i++)
		cin >> a[i];
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=n-i;j++){
			swap(a[j],a[j+1]);
			ans++;
		}
	}
	cout << ans << endl;
	
	return 0;
}

逆序对与排序的稳定性

逆序对

上题的实质是求逆序对。

对于一个数列，如1,2,7,4,3,8,9,5,6共9个数，其<序号，数值>对<i, $a_i$ >是<1,1>, <2,2>, < 3,7 >, <4,4>, <5,3>, <6,8>, <7,9>, <8,5>, <9,6>。

所谓的逆序对是，对于<i, $a_i$ >和<j, $a_j$ >而言，当 $i<j$ 时 $a_i>a_j$ 。

对于上例而言:

<1,1>没有逆序对
<2,2>没有逆序对
< 3,7>有4个，分别是<4,4>, <5,3>, <8,5>, <9,6>
<4,4>有1个，<5,3>
<5,3>没有逆序对
<6,8>有2个，分别是 <8,5>, <9,6>
<7,9>有2个，分别是 <8,5>, <9,6>
<8,5>没有逆序对
<9,6>没有逆序对

上例共有9个逆序对

冒泡排序的本质是消除逆序对，进而达到数值对位的目的。用冒泡排序的交换次序可以统计出逆序对的个数，但其计算复杂度是O(n²)相对较慢。

对于归并排序来说，当两个元素相等时并不交换位置，只有真正逆序时交换位置，并且其计算复杂度是O(nlog²n)，相对较快，所以求逆序对及其个数可以用归并排序实现。

排序的稳定性

当数值大小相等时，不能使其初始相对位置改变的排序是稳定排序，如数组排序中的：冒泡排序，插入排序，归并排序，计数排序，桶排序和基数排序。可以用algorithm包中的stable_sort函数实现。

当数值大小相等时，不能保证其初始相对位置不变的排序是非稳定排序，如数组排序中的：选择排序，堆排序，快速排序和希尔排序。可以用algorithm包中的sort函数实现。

algorithm中stable_sort和sort函数可以给出排序结果，但统计逆序对的工作仍需采用传统的排序算法自己完成。

用归并排序统计逆序对

[+]

#include <iostream>
using namespace std;

int a[100],r[100],ans=0,n;

void merge(int s,int t){
	if(s==t) return ;
	int mid = (s+t)/2;
	merge(s,mid);
	merge(mid+1,t);
	
	int left=s,right=mid+1,p=s;
	while(left<=mid && right<=t){
		if(a[left]<=a[right]){
			r[p]=a[left];
			p++;
			left++;
		}else{
			r[p]=a[right];
			p++;
			right++;
			ans = ans + mid-left+1; //统计逆序对，跨域了(left,mid]之间的元素个数 
		}
	}
	while(left<=mid){
			r[p]=a[left];
			p++;
			left++;
	}
	while(right<=t){
		r[p]=a[right];
		p++;
		right++;
	}
	for(int i=s;i<=t;i++)
		a[i] = r[i];
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++)
		cin >> a[i];
	
	merge(0,3);
	
	cout << ans << endl;
	cout << a[0]; 
	for(int i=1;i<n;i++)
		cout  << "," << a[i] ;
	cout << endl; 
	
	return 0;
}

Exercise

谁考了第k名，http://noi.openjudge.cn/ch0110/01/[+]

#include <iostream>
#include <algorithm>
using namespace std;

struct student {
		string id;
		float score;
}s[100];

bool comp(student a,student b){
		return a.score > b.score;
}

int main(){
		int n,k;
		
		cin >> n >> k;
		for(int i=0;i<n;i++){
				cin >> s[i].id >> s[i].score;
		}
		sort(s,s+n,comp);
		
		cout << s[k-1].id << " " << s[k-1].score << endl;
		
		return 0;
}

奇数单增序列，http://noi.openjudge.cn/ch0110/02/[+]

#include <iostream>
#include <algorithm>
using namespace std;
int a[500];
bool comp(int a,int b){
	return a < b;	
}

int main(){
		int n,tmp,p=0;
		cin >> n;
		for(int i=0;i<n;i++){
				cin >> tmp;
				if(tmp%2==1)
						a[p++]=tmp;
		}
		sort(a,a+p,comp);
		
		cout << a[0];
		for(int i=1;i<p;i++)
				cout << "," << a[i];
		cout << endl;
		
		return 0;
}

成绩排序，http://noi.openjudge.cn/ch0110/03/[+]

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

struct Score {
	string name;
	int score;
};

Score s[100];
int n;

bool comp(Score a,Score b){
	if(a.score>b.score)
		return true;
	else if(a.score==b.score){
		if(a.name.compare(b.name)<0)
			return true;
	}
	return false;
}

int main(){

	cin >> n;
	for(int i=0;i<n;i++)
		cin >> s[i].name >> s[i].score;

	sort(s,s+n,comp);		
	
	for(int i=0;i<n;i++)
		cout << s[i].name << " " << s[i].score << endl;
		
	return 0;
}

奖学金，http://noi.openjudge.cn/ch0110/04/[+]

#include <iostream>
#include <algorithm>
using namespace std;

struct Student{
	int no;
	int chinese;
	int math;
	int english;
	int total;
};

Student s[305];
int n;

bool comp(Student a,Student b){
	if(a.total>b.total)
		return true;
	else if(a.total == b.total)
		if(a.chinese>b.chinese)
			return true;
		else if(a.chinese == b.chinese)
			if(a.no<b.no)
				return true;		
	return false;
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		s[i].no=i;
		cin >> s[i].chinese >> s[i].math >> s[i].english;
		s[i].total = s[i].chinese+s[i].math+s[i].english;
	}	
	
	sort(s+1,s+n+1,comp);
	
	for(int i=1;i<=5;i++){
		cout << s[i].no << " " << s[i].total << endl;
	}
	
	return 0;
}

分数线划定，http://noi.openjudge.cn/ch0110/05/[+]

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,line;

struct Candidate{
	int id;
	int score;
};

Candidate candi[5005];

bool comp(Candidate a,Candidate b){
	if(a.score>b.score)
		return true;
	else if(a.score == b.score)
		if(a.id < b.id)
			return true;
	return false;
}

int main(){
	cin >> n >> m;
	for(int i=0;i<n;i++)
		cin >> candi[i].id >> candi[i].score;
	sort(candi,candi+n,comp);
	int p = m*1.5;
	int cnt = 1;
	for(int i=0;i<n;i++){
		if(cnt<p){
			cnt++;
		}else{
			line = candi[i].score;
			break;
		}
	}	
	cnt = 0;
	for(int i=0;i<n;i++){
		if(candi[i].score>=line){
			cnt++;
		}else{
			break;
		}
	}
	cout << line << " " << cnt << endl;
	for(int i=0;i<cnt;i++)
		cout << candi[i].id << " " << candi[i].score << endl;
	
	return 0;
}

整数奇偶排序，http://noi.openjudge.cn/ch0110/06/[+]

#include <iostream>
#include <algorithm>
using namespace std;

int n,a[20],b[20],al=0,bl=0;

bool comp(int a,int b){
	return a>b;	
}

int main(){
	for(int i=0;i<10;i++){
		cin >> n;
		if(n%2==0){
			b[bl++]=n;
		} else{
			a[al++]=n;
		}
	}
	sort(a,a+al,comp);
	sort(b,b+bl);
	for(int i=0;i<al;i++)
		cout << a[i] << " ";
	for(int i=0;i<bl;i++)
		cout << b[i] << " ";
	cout << endl;
	
	return 0;
}

合影效果，http://noi.openjudge.cn/ch0110/07/[+]

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

double f[40],m[40],h;
int n,fl=0,ml=0;
string name;

bool comp(double x,double y){
	return x>y;
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> name >> h;
		if(name.compare("male")==0){
			m[ml++]=h;
		}
		if(name.compare("female")==0){
			f[fl++]=h;
		}
	}
	sort(m,m+ml);
	sort(f,f+fl,comp);
	for(int i=0;i<ml;i++)
		printf("%.2f ",m[i]);
	for(int i=0;i<fl;i++)
		printf("%.2f ",f[i]);
	cout << endl; 
	
	return 0;
}

病人排队，http://noi.openjudge.cn/ch0110/08/[+]

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

struct P{
	string no;
	int age;
};

P p1[100],p2[200];

int n,age,l1=0,l2=0;
string no;

bool comp(P a,P b){
	return a.age > b.age;
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> no >> age;
		if(age>=60){
			p1[l1].no = no;
			p1[l1].age = age;
			l1++;
		}else{
			p2[l2].no = no;
			p2[l2].age = age;
			l2++;
		}
	}	
	stable_sort(p1,p1+l1,comp);
	for(int i=0;i<l1;i++)
		cout << p1[i].no << endl;
	for(int i=0;i<l2;i++)
		cout << p2[i].no << endl;
		
	return 0;
}

明明的随机数，http://noi.openjudge.cn/ch0110/09/[+]

#include <iostream>
#include <algorithm>
using namespace std;

int n,num[105];

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> num[i];
	}
	sort(num,num+n);
	int flag = num[0],cnt=1;
	for(int i=1;i<n;i++){
		if(num[i]!=flag){
			flag=num[i];
			cnt ++;
		}
	}
	cout << cnt << endl; 		
	flag = num[0];
	cout << flag;
	for(int i=1;i<n;i++){
		if(num[i]!=flag){
			flag=num[i];
			cout << " " << flag;
		}
	}
	cout << endl;
	
	return 0;
}

单词排序，http://noi.openjudge.cn/ch0110/10/[+]

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;

set<string> words;
string s;

int main(){
	while(cin>>s){
		words.insert(s);
	}
	for(set<string>::iterator p=words.begin();p!=words.end();p++){
		cout << *p << endl;
	}
	
	return 0;
}

出现次数超过一半的数，http://noi.openjudge.cn/ch0113/28/[+]

#include <iostream>
#include <algorithm>
using namespace std;

int a[1005],b[1005],n,ans=10000;

int main(){
	
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i];
		b[a[i]+50] ++;
	}
	
	for(int i=0;i<=100;i++){
		if(b[i]>n/2){
			ans = i-50;
		}
	}
	if(ans<10000)
		cout << ans << endl;
	else
		cout << "no" << endl;
		
	return 0;
}

统计字符数，http://noi.openjudge.cn/ch0113/29/[+]

#include <iostream>
#include <string>
using namespace std;

string s;
int n,a[1005],maxc=0,ans;

int main(){
	cin >> s;
	n = s.size();
	for(int i=0;i<n;i++){
		a[s[i]-'a']++;
	}
	for(int i=0;i<30;i++){
		if(a[i]>maxc){
			maxc = a[i];
			ans = i;
		}
	}
	
	cout << char(ans+'a') << " " << maxc << endl;
		
	return 0;
}

参考文献

董永建，信息学奥数一本通（C++）第五版。
http://noi.openjudge.cn

辽师张大为@https://daweizh.github.io/csp/