跳至正文

Noip 2005 篝火晚会

  • OI路程

  纠结了不知道好久,最后发现题目的意思理解错了(b1, b2, ….., bm)这些b是任意选择的, 也就是说可以选择(1, 5, 7)之类的。那么把题目理解正确了就好说了,输出的就是没有站好的人数(就是位置站错了的),所以就很简单了。
  首先一个初始列队,一个目标列队(即每个人理想的左右的人。)如果无法实现那么输出-1,不然的话就开始判断在正确位置上的人的个数,然后再用n-这个个数(要最大)。
  代码如下:

#include <stdio.h>
#include
<stdlib.h>
int left[50000],
right[50000], p[50000];
int hash[50000], bits[50000];
int n;

void output(int k)
{
        printf("%d\n",
k);
        getch();
        exit(0);
}

void init(void)
{
        int i, j;
        scanf("%d",
&n);
        for(i = 0; i < n; i++){
                scanf("%d%d", &left[i],
&right[i]);
                left[i]–,
right[i]–;
        }

        j = 0;
        for(i =
0; i < n; i++){
                p[i] =
j;
                if(bits[left[j]]){
                        j =
right[j];
                }else{
                        j =
left[j];
                }
                if(bits[j]){
                        output(-1);
                }
                bits[j] = 1;
        }
}

#define
loop(j)
do{\
        for(i = 0; i < n; i++){\
                if(p[j] >= i){\
                        hash[p[j] – i]++;\
                }else{\
                        hash[p[j] – i + n]++;\
                }\
        }\
        for(i = 0; i < n; i++){\
                if(hash[i] > max){\
                        max = hash[i];\
                }\
        }\
}while(0)

int main(void)
{
        int i, max = 0;
        init();
        loop(i);
        memset(hash,
0, sizeof(hash));
        loop(n – i – 1);
        output(n – max);
}

发表回复

您的电子邮箱地址不会被公开。