###题目链接###

题目大意:有 n 个正整数,每个正整数代表一个成语,正整数一样则成语相同。同一个正整数最多只会出现 3 次。

求一种排列,使得这个排列中,相同成语的间隔最小值最大,输出这个最小间隔的最大值。

相同成语的间隔为这两者中间的成语个数。

特别地,当每种成语都只出现一次时,把最小间隔的最大值视为 

分析:

1、若成语最大出现的次数是 2 时:比如有两个不同的成语 1  2 ,他们都出现过两次,那么为了使得最小间隔要最大,最好的构造就是两个 1 的间隔等于两个 2 的间隔。

       1    2     X X X X X    1    2        ( X 代表别的成语)

这样就可以使得出现过两次的成语,他们的间隔都相同了,不会有哪一个更小。那么设 res = 只出现一次的成语个数,设 a = 出现为两次的成语种类数。

则 res = n - 2 * a ,答案就是:res + (a - 1)

2、那么对于成语没有出现次数为 2 ,有出现次数为 3 时,也可以这样构造。   

1  2  3     X X X    1  2  3   X X     1  2  3

这样你会发现,1 2 3 这三个成语的最小间隔都一样,那由于这里 X 为奇数(X=5),分占两边则必有一边更少,那么少的这一边就是最小间隔了。

设 res = 出现一次的成语个数,a = 出现三次的成语种类数。则 res = n - 3 * a,答案就是:res + (a - 1)。

3、那么对于既有两次的又有三次出现的成语,也可以用上面的思想构造:

由于为了使最小间隔最大,而对于出现三次的成语,最好是一个在最左一个在最右,一个在最中间。而对于出现两次的成语,由于没有 “中间第三个成语”的限制,那么为了加大出现三次的成语的间隔数,最好的方法就是先最左最右排完出现三次的成语,然后才排出现两次的成语。

比如这有出现三次的:1  2  3,出现两次的  4  5 。

1  2  3   4  5           XX     1  2  3           X X X        4  5   1  2  3

这样可以最大限度的保证最小间隔尽量小且 1 与 1 ,2 与 2 ,3与 3 的最小间隔相同(对于成语出现两次的也是一样的,它们间隔都相同)

但这里有个极限想法:如果出现两次的成语个数很多,导致它们一直往中间靠拢,可能会使某个出现两次的成语的间隔会小于出现三次的成语的间隔,则同时求出来然后去 min 即可。

设 res = 出现一次的成语个数,x = 出现两次的成语种类数,y = 出现三次的成语种类数。

则有:res = n - 2 * x - 3 * y,答案为:min(res + y + x - 1, res / 2 + x + y - 1)

hhh 然后这个 min 其实没用,可以从公式中看出,右边(成语出现为三次的最小间隔)一定会小于左边(成语出现为两次的最小间隔)。

然后由于数据太大,记录成语出现的次数除非开 map  或 离散化。

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100008],b[100008],c[100008], vis[100008];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) c[i] = lower_bound(b + 1, b + len + 1, a[i]) - b, vis[c[i]] ++;//离散化
    int x = 0, y = 0;
    for (int i = 1; i <= len; i++){
        if (vis[i] == 2) x++;
        else if (vis[i] == 3) y++;
    }
    int res, ans;
    if ((!x) && (!y)){
        ans = n;
    }
    else if (x&&(!y)){
        res = n - 2 * x;
        ans = res + x - 1;
    }
    else if ((!x)&&y){
        res = (n - 3 * y) / 2;
        ans = res + y - 1;
    }
    else{
        res = n - 2 * x - 3 * y;
        //ans = min(res + y + x - 1, res / 2 + x + y - 1);
        ans=res / 2 + x + y - 1;
    }
    printf("%d\n", ans);
}
01-06 21:11