首页 技术 正文
技术 2022年11月23日
0 收藏 564 点赞 4,922 浏览 1815 个字

题目

题目描述

给N个整数,每个整数只能是1,2,或3。现在需要对这个整数序列进行从小到大排序,问最少需要进行几次交换。N(1 <= N <= 1000)

样例输入

9
2
2
1
3
3
3
2
3
1

样例输出

4

解题思路

这个题目我没有做出来,想到一个思路,提交之后返回一个wa。后来看了一下题解,才知道自己错在什么地方。现在来回顾一下。

错误思路

我首先统计了1,2,3的个数,记为cnt1,cnt2,cnt3。然后统计在前cnt1个位置有多少个数字不是等于1的,统计在中间cnt2个位置有多少不是等于2的,统计在后面cnt3个位置有多少不是等于3的,这些统计结果分别记为tot1,tot2,tot3。然后经过一系列的神操作,我得到一个结论:tot = tot1+tot2+tot3,当tot为偶数的时候结果就是tot/2,当tot为奇数的时候结果就应该是(tot-3)/2 + 2。提交结果发现第七组样例过不了。后来想了一小会,没有找到推翻这个结论的样例,就开始找题解了。后来我根据这个思路的漏洞找到了一组样例223311,按照这个结论输出为3,其实结果是4。

正确思路

看完题解之后发现,之前找规律的时候思路不严谨,有地方没有认真证明,而是凭靠直觉解题,这是做题的大忌,得改。

首先我们同样统计出cnt1,cnt2,cnt3,然后需要统计的不是简单的tot1,tot2,tot3了,我们应该将前cnt1个位置中有多少2,有多少为3分别统计,分别记为cnt12,cnt13。同样我们要得到cnt21,cnt23,cnt31,cnt32。

第一步:我们在进行数字交换的时候如果在前cnt1个位置上发现有2,并且在中间cnt2个位置上有1,这种时候我们应该优先交换这两个数字,这样1跟2都出现在应该在的位置。然后我们看前cnt1个位置上有没有3,如果有的话应该和后面cnt3个位置上的1进行交换。同理交换所有的这样的数字。

第二步:在进行完上面的操作之后剩下的数字都是什么样的呢,如:312,这个序列,我们需要进行两次交换才能将三个数字都放在应该在的位置。所以我们得到的结论如下:

首先按照按照第一步计算需要交换的次数,然后剩下的数字都需要用第二步来交换。

解题代码

/*
ID: yinzong2
PROG: sort3
LANG: C++11
*/
#define MARK
#include <cstdio>
#include <iostream>
using namespace std;int N;
int num[1010];int main() {
#ifdef MARK
freopen("sort3.in", "r", stdin);
freopen("sort3.out", "w", stdout);
#endif // MARK
cin >> N;
int cnt[3] = {0};
for (int i = 0; i < N; i++) {
cin >> num[i];
cnt[num[i]-1]++;
}
int cnt12 = 0, cnt13 = 0;
for (int i = 0; i < cnt[0]; i++) {
if (num[i] == 2) {
cnt12++;
} else if (num[i] == 3) {
cnt13++;
}
}
int cnt21 = 0, cnt23 = 0;
for (int i = cnt[0]; i < cnt[0]+cnt[1]; i++) {
if (num[i] == 1) {
cnt21++;
} else if (num[i] == 3) {
cnt23++;
}
}
int cnt31 = 0, cnt32 = 0;
for (int i = cnt[0]+cnt[1]; i < cnt[0]+cnt[1]+cnt[2]; i++) {
if (num[i] == 1) {
cnt31++;
} else if (num[i] == 2) {
cnt32++;
}
}
int ans = 0;
// 第一步操作
ans += min(cnt12, cnt21); cnt12 -= min(cnt12, cnt21); cnt21 -= min(cnt12, cnt21);
ans += min(cnt13, cnt31); cnt13 -= min(cnt13, cnt31); cnt31 -= min(cnt13, cnt31);
ans += min(cnt23, cnt32); cnt23 -= min(cnt23, cnt32); cnt32 -= min(cnt23, cnt32);
// 剩下的数字需要按照第二步来操作,每个312这种序列都需要用2次交换
ans += ((cnt12 + cnt13)*2);
cout << ans << endl;
return 0;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,183
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,644
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,488
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,260
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,897
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,062