usaco-2.1-sort3-pass

这个题是水题?呵呵,不一定呵。

/*
ID: qq104801
LANG: C++
TASK: sort3
*/

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;
int n;

void test()
{    
    freopen("sort3.in","r",stdin);
    freopen("sort3.out","w",stdout);
    cin>>n;
    //cout<<n<<endl;
    int i,x;
    vector<int> v;
    vector<int>::iterator it1;
    multiset<int> s;
    multiset<int>::iterator it2;
    for(i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
        s.insert(x);
    }
    int c12=0,c13=0,c21=0,c23=0,c31=0,c32=0;
    for(it1=v.begin(),it2=s.begin();it1!=v.end(),it2!=s.end();++it1,++it2)
    {
        if(*it1!=*it2)
        {
            if(*it2==1)
            {
                if(*it1==2)c12++;
                if(*it1==3)c13++;
            }
            if(*it2==2)
            {
                if(*it1==1)c21++;
                if(*it1==3)c23++;
            }
            if(*it2==3)
            {
                if(*it1==1)c31++;
                if(*it1==2)c32++;
            }
        }
    }
    int ans=c21+c31+(c21>c12?c23+c21-c12:c32+c12-c21);
    cout<<ans<<endl;
}

int main () 
{        
    test();        
    return 0;
}

test data:

USER: cn tom [qq104801]
TASK: sort3
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.008 secs, 3508 KB]
   Test 2: TEST OK [0.008 secs, 3508 KB]
   Test 3: TEST OK [0.003 secs, 3508 KB]
   Test 4: TEST OK [0.005 secs, 3508 KB]
   Test 5: TEST OK [0.005 secs, 3508 KB]
   Test 6: TEST OK [0.005 secs, 3508 KB]
   Test 7: TEST OK [0.008 secs, 3508 KB]
   Test 8: TEST OK [0.008 secs, 3508 KB]

All tests OK.

YOUR PROGRAM ('sort3') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.

Here are the test data inputs:

------- test 1 ----
3
2
1
3
------- test 2 ----
2
1
1
------- test 3 ----
6
1
2
3
2
3
1
------- test 4 ----
9
2
2
1
3
3
3
2
3
1
------- test 5 ----
20
1
1
3
2
1
1
1
3
2
1
3
3
2
1
3
1
1
2
3
1
------- test 6 ----
50
1
1
1
3
1
3
2
1
2
3
3
1
3
2
1
1
2
3
2
2
3
3
2
3
2
2
3
1
1
1
1
1
1
1
3
1
1
2
2
3
1
1
3
3
2
1
1
1
3
2
------- test 7 ----
100
3
2
2
3
1
.........
/***********************************************

看书看原版,原汁原味。

不会英文?没关系,硬着头皮看下去慢慢熟练,才会有真正收获。

没有原书,也要网上找PDF来看。

网上的原版资料多了去了,下载东西也到原始下载点去看看。

你会知其所以然,呵呵。

***********************************************/

原文地址:https://www.cnblogs.com/dpblue/p/3952410.html