USACO 2.1.3 sort3

IOI经典题目

题意：交换排序的方式，如何以最少的次数使得目标序列有序

解法：

本题目中数字都来自集合{1， 2， 3}，

将序列排序，统计1, 2, 3的个数，标记为num1, num2, num3

统计num1段中2,3的个数，num2段中1,3的个数，num3段中1,2的个数，分别标记为a2,a3,b1,b3,c1,c2

对应的pair只需要交换一次就有序

分别需要min(a2,b1) min(a3, c1)...等

再统计剩余数组中不在本身位置上的个数y，

总的个数就是3段pair可交换数之和，以及加上y * 2 / 3

/*
ID: lsswxr1
PROG: sort3
LANG: C++
*/
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
using namespace std;

#define USACO
#ifdef USACO
#define cin fin
#define cout fout
#endif
//////////////////////////////////////////////////////////////////////////
///宏定义
const int  INF = 1000000000;
const int MAXN = 2001;
const int maxn = MAXN;
///全局变量 和 函数
int N;
int ori[maxn];
int sarr[maxn];
int a2, a3, b1, b3, c1, c2;
int num1, num2, num3;
int main()
{
#ifndef USACO
    freopen("D:\\input.txt", "r", stdin);
#endif

#ifdef USACO    
    ofstream fout ("sort3.out");
    ifstream fin ("sort3.in");
#endif   

    while (cin >> N)
    {
        a2 = a3 = b1 = b3 = c1 = c2 = 0;
        num1 = num2 = num3 = 0;
        for (int i = 0; i < N; i++)
        {
            int num;
            cin >> num;
            ori[i] = sarr[i] = num;
            if (num == 1) num1++;
            else if (num == 2) num2++;
            else if (num == 3) num3++;
        }
        sort(sarr, sarr + N);
        for (int i = 0; i < num1; i++)
        {
            if (ori[i] == 2) a2++;
            else if(ori[i] == 3) a3++;
        }
        for (int i = num1; i < num1 + num2; i++)
        {
            if (ori[i] == 1) b1++;
            else if(ori[i] == 3) b3++;
        }
        for (int i = num1 + num2; i < N; i++)
        {
            if (ori[i] == 1) c1++;
            else if(ori[i] == 2) c2++;
        }
        int noMove = 0;
        for (int i = 0; i < N; i++)
        {
            if (ori[i] == sarr[i])
            {
                noMove++;
            }
        }

        int x1 = min(a2, b1);
        int x2 = min(a3, c1);
        int x3 = min(b3, c2);
        int rests = N - x1 * 2 - x2 * 2 - x3 * 2 - noMove;
        int ans = x1 + x2 + x3 + rests * 2 / 3;

        cout << ans << endl;
    }

    ///结束
    return 0;
}

原文链接: https://www.cnblogs.com/rayforsure/p/3524357.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍