排序题目 | Hwikb

本文介绍几道排序相关的练习题，这几道题也比较有趣。

错误票据

题目描述

某涉密单位下发了某种票据，并要在年终全部收回。每张票据有唯一的 ID号。全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。你的任务是通过编程，找出断号的 ID 和重号的 ID 。假设断号不可能发生在最大和最小号。

输入描述：要求程序首先输入一个整数N(N<100)表示后面的行数，接着读入N行数据。每行数据长度不相等，是用空格分开的若干个(不大于100个)正整数(不大于10e5)。

输出描述：要求程序输出1行，含两个整数m，n,用空格分隔，其中，m表示断号ID，n表示重号ID。

题目分析

这道题如果能直接得到一个数组，那就很容易就可以解决，不管是排序还是什么。这道题的难点在于怎么读入数据。

介绍一下怎么按行读入，getline()，接收一个字符串，可以接收空格并输出，需要包含”#include< string >”。需要注意的是当同时使用cin>>和getline()时，在cin>>输入流完成之后，getline()之前，需要通过

str="\n";
getline(cin,str);

这样的方式将回车符作为输入流cin以清除缓存，如果不这样在控制台上就不会出现getline()的输入提示，而是直接跳过，因为程序默认将之前的变量作为输入流。

现在已经将读入的整行数字以字符串的形式保存，接下来就是需要将其读入数组，stringstream是字符串流。流和存储在内存中的字符串string对象是绑定的，可以在多种数据类型之间实现自动格式化。包含在#include< sstream >中。

int value=520;
stringstream ssin;
ssin<<value;
int iConvertValue;
ssin>>iConvertValue;

第三行是将流的内容转化成字符串，第五行又将流的内容以int的类型输入给iConvertValue。

代码部分

#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;
int a[100001];

int main()
{
	int n,value;
	int maxvalue=0,minvalue=0;
	int m,q;
	cin>>n;
	string line;
	getline(cin,line);
	while(n--)
	{
		getline(cin,line);
		stringstream ssin(line);
		while(ssin>>value)
		{
			if(value>maxvalue) maxvalue=value;
			if(value<minvalue) minvalue=value; 
			a[value]++;
		}
	}
	for(int j=minvalue;j<=maxvalue;j++)
	{
		if(a[j]==0)  m=j;
		if(a[j]==2)  q=j;
	}
	cout<<m<<" "<<q;	
}

因为数字的范围是小于1e5的，所以我先建立1e5个桶，然后把这些数据扔到桶里，在(minvalue,maxvalue)这个范围内，哪个桶里没有数据，那它就是缺少的数值，哪个桶里有2个数据，那它就是重复的那一个。

封闭图形个数

问题描述

蓝桥王国，数字的大小不仅仅取决于它们的数值大小，还取决于它们所形成的“封闭图形”的个数。

数字1,2,3,5,7中没有形成封闭图形，而数字0,4,6,8分别形成了一个封闭图形，数字8则形成了2个封闭图形，并且封闭图形的个数是可以累加的，例如68，一共就有三个封闭图形。

在比较两个数的大小时，如果他们封闭图形个数不同，那么封闭图形个数较多的更大。如果封闭图形的个数是相等的，那么数值大的更大。

输入格式：第一行包含一个整数n,表示给定的数字个数；第二行包含n个待排序的数字。
输出格式：输出一行，就是对应排序后的结果，每两个数字之间用一个空格分隔。

题目分析

首先那得确定一下这个数字里面一共有几个洞，可以把数字转化成字符串，然后逐个字符看一下，这里我建立了两个哈希表，一个里面是有一个洞的数字，另一个是有两个洞的数字，都是字符型的，这样方便查找。
需要比较的是一个数里面洞的个数，如果相等时也需要比较数值的大小，这里可以用向量vector< pair< int,int> >,里面有两个数值，先比第一个，相等的话就比第二个。这样排序完成之后将向量里面第二个值赋给数组即可。

代码部分

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_set>
using namespace std;
void closefigure(int arr[],int n)
{
	unordered_set<char> str2={'0','4','6','9'};
	unordered_set<char> str3={'8'};
	vector<pair<int,int> > close_data;
	for(int i=0;i<n;i++)
	{
		int hole_data=0;
		string m=to_string(arr[i]);
		for(char c:m)
		{
			if(str2.count(c)) hole_data+=1;
			if(str3.count(c)) hole_data+=2;
		}
		close_data.push_back({hole_data,arr[i]});
	}
	sort(close_data.begin(),close_data.end());
	for(int i=0;i<n;i++) arr[i]=close_data[i].second;
}


int main()
{
	int a;
	cin>>a;
	int *b=new int[a];
	for(int i=0;i<a;i++)
	{
		cin>>b[i];
	}
	closefigure(b,a);
	for(int i=0;i<a;i++)
	{
		cout<<b[i]<<" ";
	}
	return 0;

}

三国游戏

小蓝正在玩一款游戏。游戏中魏(X)蜀(Y)吴(Z)三个国家拥有一定量的士兵X，Y，Z（一开始都认为是0）。游戏有n个可能发生的时间，每个时间之间相互独立且最多发生一次，当第i个时间发生时会分别让X，Y，Z增加A_i,B_i,C_i.

当游戏结束时(有所时间发生与否已经确定)，如果X，Y，Z的其中一个大于另外两个之和，我们认为其获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?如果不存在任何能让某国获胜的情况，请输出 −1。

输入格式：输入的第一行包含一个整数n.
第二行包含n个整数表示A_i,相邻整数之间使用一个空格分隔。
第三行包含n个整数表示B_i,相邻整数之间使用一个空格分隔。
第四行包含n个整数表示C_i,相邻整数之间使用一个空格分隔。

输出格式：输出一行表示答案。

问题分析

这个题有几个困惑点，就是每个事件是等概率发生的，那到底应该怎么确定应该是哪几个事件发生呢？到底是哪个国家获胜呢，可能本来这个国家兵力雄厚，但发生了一个事件，他的兵力又不雄厚了。

在此从哪个国家获胜为出发点，因为一共就只有三个国家，分三种情况也就可以了。假如现在我们已经确定让魏国获胜了，那我们应该确定让哪几个事件发生呢。这里就是用到贪心算法了，哪个事件对魏国最有利，就先让哪个事件发生。对魏国有利，就意味着(X[i]-Y[i]-Z[i])是大于零的，所以让t[i]=X[i]-Y[i]-Z[i],并且对t[i]累加，累加到它是小于等于0的时候，就可以确定有多少事件发生了。然后再计算另外两个国家获胜时最多的事件个数，三者取最大即可。

#include<iostream>
#include<algorithm>
#define int long long 
using namespace std;
const int M=100010;
int a[M],b[M],c[M],t[M],n;
signed get(int*x,int*y,int*z)
{
	for(int i=0;i<n;i++)
	{
		t[i]=x[i]-y[i]-z[i];
	}
	sort(t,t+n,greater<int>());
	if (t[0]<=0) return 0;
	for(int i=1;i<n;i++)
	{
		t[i]+=t[i-1];
		if(t[i]<=0)  return i;
	}
	return n;
}

signed main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=0;i<n;i++) cin>>c[i];
	int res=max({get(a,b,c),get(b,a,c),get(c,a,b)});
	cout<<(res==0?-1:res);
	return 0; 
	 
}