ZigZagK的博客
[划水,贪心]Codeforces1008C【Reorder the Array】题解
ZigZagK
2018年8月16日 23:28
Codeforces
查看标签

题目概述

给出一个序列 $\{a_n\}$ ，重排列这个序列使得新序列 $\{b_n\}$ 中 $b_i>a_i$ 尽量多。

解题报告

这啥啊……田忌赛马？将 $\{a_n\}​$ 排个序，维护四个指针 $l,r,L,R​$ ：

  1. $a_l>a_L$ ：$ans+1,l+1,L+1$ 。（能干就干）
  2. $a_r>a_R$ ：$ans+1,r-1,R-1$ 。（能干就干）
  3. Otherwise：$l+1,R-1$ 。（劣马抵好马）

不过因为这道题没有小于扣分机制，所以 $n-$数量最多的数的数量 好像就是答案……貌似还可以其他各种贪心……

示例程序

脑抽了又开了一个数组 $\{b_n\}$ 。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;

int n,a[maxn+5],b[maxn+5],ans;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);for (int i=1;i<=n;i++) b[i]=a[i];
    for (int i=1,l=1,r=n,L=1,R=n;i<=n;i++){
        if (a[l]>b[L]) {l++;L++;ans++;continue;}
        if (a[r]>b[R]) {r--;R--;ans++;continue;}
        l++;R--;
    }
    return printf("%d\n",ans),0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！