CodeForces - 1007A （思维+双指针）

佚名 6年前 (2019-11-22) 算法 1873人围观抢沙发百度已收录

题意

https://vjudge.net/problem/CodeForces-1007A

对一个序列重排，使得新的数比原来的数大对应的位置个数最多。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路

举个栗子，比如1 2 2 3 3 3 3 4 5，那么对于一个数，肯定是用比他大的最小的去覆盖他，这样后面较大的数就有更多的机会被覆盖了。比如用2覆盖1，但不能用5覆盖1，因为这样的话4就不会被覆盖了。再考虑乱序的，比如 2 1 3 5 3 3 4 3 2，一样的，用2覆盖1，用3覆盖2，和有序的序列其实并无区别，所以我们直接拍个序，用双指针遍历即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int a[N];
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    int i=1,j=1;
    for(;i<=n;i++)
    {
        if(a[i]>a[j])
        {
            j++;
        }
    }
    cout<<j-1<<endl;
    return 0;
}