4 条题解

  • 1
    @ 2026-9-23 16:19:41

    贪心考虑,我们希望每次交换的效果尽可能的好。因此容易想到先把互相在对方位置的元素交换,这样一次操作使得两个错误的变正确。

    这时候错误的1,2,3数量一定相等(仔细想想为什么)。切形成错排结构(因为不错排的上一步被处理掉了)

    容易发现一组错排形如231可以通过两次交换处理

    • 1
      @ 2025-3-20 11:12:45

      首先我们读完题目后发现,最后排完序后的样子一定是几个 11 在一起,几个 22 在一起,几个 33 在一起

      可以记录下来有几个 11、22、33 来看每一个数字的连续长度

      然后我们记录几个变量 otsots 表示在 11 的位置的不是 11 的个数,otot 表示在 11 的位置是 22的个数

      记录 toto 是在 22 的位置是 11 的个数, tsts 是在 22 的位置是 33 的个数

      显然对于每一个在 11 的位置上的 22、33 ,那么我们都要进行一次操作来把它们移走,对于每一个在 22 的位置上的 33 肯定也要进行一次操作

      但是如果从 11 到 22 的位置的个数比 从 22 到 11 的位置的个数少,那么我们就要加上这个差值

      因为如果不加上差值的话可能导致一些 11 没有回到原来的位置

      时间复杂度 O(n)O(n)

      • 0
        @ 2026-9-22 15:00:53
        #include<bits/stdc++.h>
        using namespace std;
        const int N=1e7+5;
        int a[N],cnt[4],b[4];
        signed main()
        {	
        	ios::sync_with_stdio(0);
        	cin.tie(0);
        	
        	int n;
        	cin>>n;
        	
        	for(int i=1;i<=n;i++)
        	{
        		cin>>a[i];
        		cnt[a[i]]++;
        	}
        	
        	for(int i=1;i<=cnt[1];i++)//第一段 
        	{
        		if(a[i]==1) continue;
        		b[a[i]]++;
        	}
        	
        	for(int i=cnt[1]+1;i<=cnt[1]+cnt[2];i++)//第二段
        	{
        		if(a[i]==2) continue;
        		b[a[i]]++;
        	}
        	
        	cout<<b[3]+max(b[1],b[2])<<'\n';//前两段出现了3是必须要换的,直接加上;第一段出现了 2,第二段出现了 1,则 b[]较大值为交换次数
        	
        	return 0;
        }
        
        #include<bits/stdc++.h>
        using namespace std;
        const int N=1e7+5;
        int a[N],cnt[4];
        
        signed main()
        {
        	ios::sync_with_stdio(0);
        	cin.tie(0);
        	
        	int n;
        	cin>>n;
        	
        	for(int i=1;i<=n;i++)
        	{
        		cin>>a[i];
        		cnt[a[i]]++;
        	}
        	
        	int x=0, y=0, ans=0;
        	
        	for(int i=1;i<=cnt[1];i++) if(a[i]==2)	x++;
        	
        	for(int i=cnt[1]+1;i<=n-cnt[3];i++)	if(a[i]==1) y++;
        	
        	for(int i=n-cnt[3]+1;i<=n;i++) if(a[i]!=3) ans++;
        	
        	cout << ans+max(x,y)*2-min(x,y)-(max(x,y)-min(x,y)) << '\n';
        }
        
        • -2
          @ 2025-3-20 9:48:59

          题意

          有n个数,其中的数只有1,2,3

          可以每次交换任意两个数

          问最少换多少次可以使得数组有序

          code

          #include <bits/stdc++.h>
          using namespace std;
          
          const int N = 1e3 + 10;
          
          int a[N], cnt[4], n;
          
          void read() {
          	cin >> n;
          	for(int i = 1; i <= n; i++) {
          		cin >> a[i];
          		cnt[a[i]]++;
          	}
          	return ;
          }
          
          void init() {
          
          }
          
          void compute() {
          	int ans = 0;
          	//将左右两端不合法的1,3交换 
          	for(int l = 1, r = n; l <= cnt[1] && r >= n - cnt[3] + 1;) {
          		while(a[l] != 3 && l <= n) l++;
          		while(a[r] != 1 && r >= 1) r--;
          		if(l <= cnt[1] && r >= n - cnt[3] + 1)
          			ans++,swap(a[l],a[r]), l++, r--;
          	}
          	//将1摆好 
          	for(int l = 1, r = n; r > l;) {
          		while(a[l] == 1 && l <= n) l++;
          		while(a[r] != 1 && r >= 1) r--;
          		if(l < r)
          		ans++, swap(a[l],a[r]), l++, r--;
          	}
          	//将3摆好 
          	for(int l = 1, r = n; r > l;) {
          		while(a[l] != 3 && l <= n) l++;
          		while(a[r] == 3 && r >= 1) r--;
          		if(l < r)
          		ans++, swap(a[l],a[r]), l++, r--;
          	}
          	cout << ans;
          }
          
          int main() {
          	ios::sync_with_stdio(0);
          	cin.tie(0), cout.tie(0);
          	read();
          	init();
          	compute();
          	return 0;
          }
          
          
          • 1

          信息

          ID
          90
          时间
          1000ms
          内存
          256MiB
          难度
          8
          标签
          (无)
          递交数
          124
          已通过
          16
          上传者