noip2005提高组篝火晚会 && nyoj59题小明活动的组织任务

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 15 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=59

这道题很早就弄到NYOJ上了,当时在研究,后来一直有事就搁浅到现在。。。想想当时如果搞的话还在上离散课,问问老师置换群就不用自己啃的那么辛苦了。。。悲剧啊~~~

大概思路:首先获得数据后判断数据是否满足各个人的需求,按简单的模拟就好一遍循环,线形时间。同时获得了目标序列的某种情况,因为是环,所以看成链的话总共有2n种情况。开始写了个O(n^2)的,没有计算数据规模,果断超时了,然后知道用置换群,啃书2天,十分难懂,这里先不说了,核心思想说一下:要求出目标环与初始环间最多有多少个元素的位置可能相同,只要求出目标环各元素值与初始环对应位置的元素值之差的结果相同的最多是多少个。十分好理解,每次做差的结果就是该元素与其应该所处的目标位置的偏移量。

for (int i=1;i<=n;i++) { temp=(n+en[i]-i)%n; searchSame[temp]++; } 这是从左向右判断,还有就是出现镜像的一种合法链,所以需要再从反方向做一边该操作。 最终获得最大的相同位置的个数。 代码如下:

#include <cstdio>  
#include <cstring>  
#include <time.h>  
using namespace std;  
#define M 50005  
int en[M],res; //en[]最终目标序列,res是en合法标记  
int need[M][3];//各个需求 [][0]标记该人是否入列,[][1],[][2]为左右需求  
int searchSame[M];//置换群求相同位置时使用  
//判断数据是否能够满足要求  
void judge(int n)  
{  
    en[1]=1;  
    for (int i=2;i<=n;i++)  
    {  
        if(need[ need[en[i-1]][1] ][0]==0)  
        {  
            en[i]=need[en[i-1]][1];  
            need[en[i-1]][0]=1;  
        }else if(need[ need[en[i-1]][2] ][0]==0)  
        {  
            en[i]=need[en[i-1]][2];  
            need[en[i-1]][0]=1;  
        }  
        else {res=-1; return;}  
    }  
    if( (need[en[n]][1]==en[1] || need[en[n]][1]==en[n-1])  
        && (need[en[n]][2]==en[1] || need[en[n]][2]==en[n-1]) )  
        return;  
    else res=-1;  
}  
//计算需求数列与原数列对比,无需移位的个数的最大值eqmax  
int calculation(int n)  
{  
    int eqmax=0;  
    int temp;  
    /*O(n^2)的时间复杂度,超时……  - - 
    for (int i=1;i<=n;i++) 
    { 
        temp=0; 
        for (int j=1;j<=n;j++) 
        { 
            if(en[(i+j-2)%n+1]==sta[j]) temp++; 
        } 
        if(eqmax<temp) eqmax=temp; 
    }*/  
    memset(searchSame,0,sizeof(searchSame));  
    temp=0;  
    for (int i=1;i<=n;i++)  
    {  
        temp=(n+en[i]-i)%n;   
        searchSame[temp]++;  
    }  
    for (int i=0;i<=n;i++)  
        if(eqmax<searchSame[i]) eqmax=searchSame[i];  
    //以下部分为上述代码的镜像操作  
    memset(searchSame,0,sizeof(searchSame));  
    for (int i=1;i<=n;i++)  
    {  
        temp=(n+en[n-i+1]-i)%n;   
        searchSame[temp]++;  
    }  
    for (int i=0;i<=n;i++)  
        if(eqmax<searchSame[i]) eqmax=searchSame[i];  
    return n-eqmax;  
}  
int main()  
{  
    //freopen("1.txt","r",stdin);  
    int N,n;  
    scanf("%d",&N);  
    while(N--)  
    {  
        memset(need,0,sizeof(need));  
        memset(en,0,sizeof(en));  
        res=0;  
        scanf("%d",&n);  
        for (int i=1;i<=n;i++)  
        {  
            scanf("%d%d",&need[i][1],&need[i][2]);  
        }  
        judge(n);  
        if(res!=-1)  
            printf("%d\n",calculation(n));  
        else printf("-1\n");  
    }  
    //printf("%f",(double)clock()/CLOCKS_PER_SEC);  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日