题目描述

C. Reorder the Array
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array [10,20,30,40], we can permute it so that it becomes [20,40,10,30]. Then on the first and the second positions the integers became larger (20>10,40>20) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals 2. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.

Input
The first line contains a single integer
n(1≤n≤10^5) — the length of the array.
The second line contains n integers a1,a2,…,an(1≤ai≤10^9) — the elements of the array.
Output
Print a single integer — the maximal number of the array’s elements which after a permutation will stand on the position where a smaller element stood in the initial array.

样例

7
10 1 1 1 5 5 3

5
1 1 1 1 1

思路：

和上篇的田忌赛马一样只不过田忌和国王的马一样，所以打平哪里可以不用考虑那么多直接让他打平就行。

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int T[maxn],K[maxn],n,w,l;
void r()
{
    for(int i=0;i<n;i++)
        scanf("%d",&T[i]);
    for(int i=0;i<n;i++)
       K[i]=T[i];
    sort(T,T+n);
    sort(K,K+n);
}
void ra()
{
    w = l =0;
    int t_slow=0,t_fast=n-1;
    int k_slow=0,k_fast=n-1;
    while(t_slow <= t_fast)
    {
        if(T[t_slow] > K[k_slow])        //情况1
        {
            w++;
            t_slow++;
            k_slow++;
        }
        else if(T[t_slow] < K[k_slow])   //情况2
        {
            l++;
            t_slow++;
            k_fast--;
        }
        else                             //情况3
        {
            if(T[t_fast] > K[k_fast])    //先别放水，让哥比完这场
            {
                w++;
                t_fast--;
                k_fast--;
            }
            else                         //1、2、3、放
            {
                if(T[t_slow] < K[k_fast])//哥不一定会输哦~~~
                    l++;
                t_slow++;
                k_fast--;
            }
        }
    }
}
int main()
{
    //freopen("1","r",stdin);
    //freopen("2","w",stdout);
    scanf("%d",&n);
    {
        r();
        ra();
        printf("%d\n",(w));
    }
    return 0;
}

总结

这道题和田忌赛马的一样。