Codeforce 370C Mittens 巧妙数学题

这道题目我一开始想错了,觉得只要排好序,再从头到尾把可以相互交换的进行下交换就可以了。。。事实证明是错的。正确的解法比较巧妙,而且写法非常好,值得学习

首先,要注意的一个规律是,假如最大的颜色数字出现的次数 为 c, c超过了n的一半,则必定无法将所有的人的颜色交换成两两不同的,而且此时颜色不同的人的数目也已经出来了

就是 (n-c)*2,于此,也很容易得出,一旦c没有超过n的一半,则肯定能够把所有人都排成不一样的,(先把相同颜色的找另一类相同颜色的互换,某一类不够了,再找另一类的来继续补充一下即可)此时的答案就是n。

进一步分析,如果是第一种情况,则一个很巧妙的处理方法就是从1到n遍历,如果当前i的颜色为颜色最多的那个颜色,则,先输出i颜色,再从非c颜色里面找不同的来匹配,当然最多只能找d个,d=n-c,如果找完d个了,就只能输出一样的颜色了,代表该人无法颜色不同。。。如果当前颜色不为i那个颜色,则先输出该颜色,再输出那个最多的颜色。

第二种情况的话,先对颜色进行排序,把相同颜色的放在一起,然后有个很巧妙的处理方法,就是某颜色的另一半=(i+c)%n.color,这个好好想想就能明白,既能遍历完整个n,又能保证不会遇到重复色(因为相同颜色在同一堆,而且这一堆的数目最大为c,所以+c再对n取模,是绝对不会匹配大到相同的颜色的)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    int date;
    int id;
    int other;
} p[5005];
bool cmp(node a,node b)
{
    return a.date<b.date;
}
bool cmp2(node a,node b)
{
    return a.id<b.id;
}
int c[105];
int main()
{
    int n,m,i,j;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(c,0,sizeof c);
        for (i=1;i<=n;i++)
        {
            scanf("%d",&p[i].date);
            p[i].id=i;
            c[p[i].date]++;

        }
        int maxn=0,index;
        for (i=1;i<=m;i++)
        {
            if (maxn<c[i])
            {
                maxn=c[i];
                index=i;
            }
        }
        if (maxn*2>n)
        {
            printf("%d
",(n-maxn)*2);
            int d=n-maxn;
            j=0;
            for (i=1;i<=n;i++)
            {
                if (p[i].date==index)
                {
                    printf("%d ",index);
                    if (d>0)
                    {
                        for (j++;j<=n && p[j].date==index;j++); //这里是个细节,j每次先要++
                        printf("%d
",p[j].date);
                        d--;
                        
                    }
                    else
                        printf("%d
",index);
                }
                else
                {
                    printf("%d %d
",p[i].date,index);
                }
            }
        }
        else
        {
            printf("%d
",n);
            sort(p+1,p+1+n,cmp);
            for (i=1;i<=n;i++)
            {
                int loc=i+maxn;
                loc%=n;
                if (loc==0) loc=n;
                p[i].other=p[loc].date;
            }
            sort(p+1,p+1+n,cmp2);
            for (i=1;i<=n;i++)
            {
                printf("%d %d
",p[i].date,p[i].other);
            }
        }

    }
    return 0;

}
原文地址:https://www.cnblogs.com/kkrisen/p/3470216.html