題意
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121125.html
標籤：其他