题意

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

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

思路

举个栗子，比如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;

}

巴特西

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

题意

思路

代码

最新文章

热门文章