注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

noip2005之第三题fire  

2008-05-24 10:46:43|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

/*第三题:fire

<题意分析>

N个人先按顺序站成一个圈,然后佳佳发布(b1,b2,……,bk)样式的命令,意思是b1换到b2的位置上,b2换到b3的位置上,……,bk换到b1的位置上,k为此命令代价。要求用最小的总命令代价调整这个圈,使之变为目标状态(就是满足所有人的喜好)。如果不能满足则输出“-1,否则输出最小代价数。*/

//myprogram:

#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("fire.in");
ofstream fout("fire.out");
int main()
{
    int a[50000];
    int b[50000];
    int c[50000];
    int d[50000];
    int e[50000];
    int i,j,k,l,m,n;
    int n_max=0;
    fin >>n;
    for (i=0;i<n;i++)
    {
        fin >>a[i]>>b[i];
    }
    c[0]=0;
    c[1]=a[c[0]]-1;
    e[c[0]]=1;
    e[c[1]]=1;
    if (c[0]==c[1])
    {
       fout <<"-1"<<endl;
       fin.close();
       fout.close();
       return 0;
    }
    for (i=0;i<n;i++)
    {
        d[i]=0;
        e[i]=0;
    }
    for (i=1;i<n-1;i++)
    {
        l=a[c[i]]-1;
        m=b[c[i]]-1;
        if (l==c[i-1])c[i+1]=m;
        else c[i+1]=l;
        if (e[c[i+1]])
        {
           fout <<"-1"<<endl;
           fin.close();
           fout.close();
           return 0;
        }
        else
        {
            e[c[i+1]]=1;
        }
    }
   
    for (i=0;i<n;i++)
    {
        j=(c[i]-i+n)%n;
        d[j]++;
        if (d[j]>n_max)n_max=d[j];
    }
    /*for (i=0;i<n;i++)
    {
        cout <<d[i]<<' ';
       
    }*/
    //cout <<endl;system("pause");
    c[0]=0;
    c[1]=b[c[0]]-1;
    e[c[0]]=1;
    e[c[1]]=1;
    if (c[0]==c[1])
    {
       fout <<"-1"<<endl;
       fin.close();
       fout.close();
       return 0;
    }
    for (i=0;i<n;i++)
    {
        d[i]=0;
        e[i]=0;
    }
    for (i=1;i<n-1;i++)
    {
        l=a[c[i]]-1;
        m=b[c[i]]-1;
        if (l==c[i-1])c[i+1]=m;
        else c[i+1]=l;
        if (e[c[i+1]])
        {
           fout <<"-1"<<endl;
           fin.close();
           fout.close();
           return 0;
        }
        else
        {
            e[c[i+1]]=1;
        }
    }
   
    for (i=0;i<n;i++)
    {
        j=(c[i]-i+n)%n;
        d[j]++;
        if (d[j]>n_max)n_max=d[j];
    }
    /*for (i=0;i<n;i++)
    {
        cout <<d[i]<<' ';
       
    }*/
    //cout <<endl;system("pause");
    fout <<n-n_max;
    fin.close();
    fout.close();
    return 0;
}

  评论这张
 
阅读(346)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017