題目描述

上課的時候總會有一些同學和前后左右的人交頭接耳，這是令小學班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當同學們的座次確定下來之后，只有有限的?DD?對同學上課時會交頭接耳。

同學們在教室中坐成了?MM?行?NN?列，坐在第?ii?行第?jj?列的同學的位置是?(i,j)(i,j)，為了方便同學們進出，在教室中設置了?KK?條橫向的通道，LL?條縱向的通道。

于是，聰明的小雪想到了一個辦法，或許可以減少上課時學生交頭接耳的問題：她打算重新擺放桌椅，改變同學們桌椅間通道的位置，因為如果一條通道隔開了?22?個會交頭接耳的同學，那么他們就不會交頭接耳了。

請你幫忙給小雪編寫一個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學生的對數(shù)最少。

輸入格式

第一行，有?55?個用空格隔開的整數(shù)，分別是?M,N,K,L,D(2 \le N,M \le 1000,0 \le K<M,0 \le L<N,D \le 2000)M,N,K,L,D(2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)。

接下來的?DD?行，每行有?44?個用空格隔開的整數(shù)。第?ii?行的?44?個整數(shù)?X_i,Y_i,P_i,Q_iXi?,Yi?,Pi?,Qi?，表示坐在位置?(X_i,Y_i)(Xi?,Yi?)?與?(P_i,Q_i)(Pi?,Qi?)?的兩個同學會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。

輸入數(shù)據保證最優(yōu)方案的唯一性。

輸出格式

共兩行。 第一行包含?KK?個整數(shù)?a_1,a_2,\ldots,a_Ka1?,a2?,…,aK?，表示第?a_1a1??行和?a_1+1a1?+1?行之間、第?a_2a2??行和?a_2+1a2?+1?行之間、…、第?a_KaK??行和第?a_K+1aK?+1?行之間要開辟通道，其中?a_i< a_{i+1}ai?<ai+1?，每兩個整數(shù)之間用空格隔開（行尾沒有空格）。

第二行包含?LL?個整數(shù)?b_1,b_2,\ldots,b_Lb1?,b2?,…,bL?，表示第?b_1b1??列和?b_1+1b1?+1?列之間、第?b_2b2??列和?b_2+1b2?+1?列之間、…、第?b_LbL??列和第?b_L+1bL?+1?列之間要開辟通道，其中b_i< b_{i+1}bi?<bi+1?，每兩個整數(shù)之間用空格隔開（列尾沒有空格）。

輸入數(shù)據 1

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

Copy

輸出數(shù)據 1

2
2 4

Copy

提示

上圖中用符號*、※、+標出了?33?對會交頭接耳的學生的位置，圖中?33?條粗線的位置表示通道，圖示的通道劃分方案是唯一的最佳方案。

NOIP 2008 普及組 第二題

代碼:

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b);

int main()
{
    int m = 0, n = 0, k = 0, l = 0, d = 0;
    int x[1010] = {0}, y[1010] = {0};
    int col[1010] = {0}, row[1010] = {0};

    scanf("%d%d%d%d%d", &m, &n, &k, &l, &d);

    for (int i = 1; i <= d; i++)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        if (x1 != x2)         //判斷x是否相等
        {                     //不等時一定存在y有相同
                              //取最小加一最大減一
            y[min(x1, x2)]++; //價值
        }
        else
        { //等于
            x[min(y1, y2)]++;
        }
    }

    for (int i = 1; i <= k; i++)
    {
//對y進行價值排序

        int max = -1;
        int index = 0;

        for (int j = 1; j < m; j++)
        {
            if (y[j] > max)
            {
                max = y[j];
                index = j;
            }
        }
        y[index] = 0;
        col[index]++;
    }

    for (int i = 1; i <= l; i++)
    {//對y進行價值排序
        int max = -1;
        int index = 0;

        for (int j = 1; j < n; j++)
        {
            if (x[j] > max)
            {
                max = x[j];
                index = j;
            }
        }
        x[index] = 0;
        row[index]++;
    }

    for (int i = 0; i < 1010; i++)
    {
        if (col[i])//遍歷x
        {
            printf("%d ", i);
        }
    }
    printf("\n");
    
    for (int i = 0; i< 1010;i++)
    {
        if (row[i])
        {
            printf("%d ", i);
        }
        
    }

    return 0; 
}

int min(int a, int b)
{
    return a < b ? a : b;
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-618805.html

到了這里，關于#P0999. [NOIP2008普及組] 排座椅的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！