前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >USACO Section 2.1 Sorting a Three-Valued Sequence

USACO Section 2.1 Sorting a Three-Valued Sequence

作者头像
全栈程序员站长
发布2022-07-12 17:06:46
1140
发布2022-07-12 17:06:46
举报

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

代码语言:javascript
复制
/*
ID: lucien23
PROG: sort3
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
void exchange(int nums[], int begin, int end, int N, int x);
int sum = 0;
int main()
{
	ifstream infile("sort3.in");
	ofstream outfile("sort3.out");
	if(!infile || !outfile)
	{
		cout << "file operation failure!" << endl;
		return -1;
	}

	int N;
	infile >> N;
	int *nums = new int[N];
	int count1, count2, count3;
	count1 = count2 = count3 = 0;
	for (int i=0; i<N; i++)
	{
		infile >> nums[i];
		switch (nums[i])
		{
		case 1:
			count1++;
			break;
		case 2:
			count2++;
			break;
		case 3:
			count3++;
			break;
		default:
			break;
		}
	}

	exchange(nums, 0, count1, N, 1);
	exchange(nums, count1, count1+count2, N, 2);

	outfile << sum << endl;

	return 0;
}

/*
 *交换时将大的交换到后面,小的交换到前面
 */
void exchange(int nums[], int begin, int end, int N, int x)
{
	int count0 = 0;
	vector<int> vecNum;
	for (int i=begin; i<end; i++)
	{
		if (nums[i] != x)
		{
			count0++;
			vecNum.push_back(nums[i]);
			nums[i] = x;
		}
	}
	sum += count0;

	sort(vecNum.begin(), vecNum.end());
	for (int i=end, j=0; i<N && count0>0; i++)
	{
		if (nums[i] == 1)
		{
			nums[i] = vecNum[j];
			j++;
			count0--;
		}
	}
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/118677.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021年12月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档