洛谷训练场——简单模拟排座位（P1056）

题目描述

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。

同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是(i,j)，为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了2个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少

输入样例　　　　　　　　　　　　　　　　输出样例

4 5 1 2 3　　　　　　　　　　　　　　　　 2

4 2 4 3　　　　　　　　　　　　　　　　　　2 4

2 3 3 3

2 5 2 4

样例最优解图析：

题目分析：
　　既然是模拟题,先看情景需求，再看样例，一看到“最好的”、“最优解” ，不禁感叹，又是一道贪心，再通过对样例图的分析可以知道，每一行每一列都有一个价值，根据每一行的价值从大到小，进行优先切分，

然后再根据列的价值对列进行切分。贪心算法中价值决定数据处理的优先级
实现思路：
　　 题目的意思很明确想让我们用有限的横、纵线将最多的交头接耳的学生分开，题目说一定相邻，那么交头接耳的人要么y相等，要么x相等，由于，线有横纵两种，所以下，x、y分别考虑。那么如何得到每一列x，y的价值呢
我最开始的想法是结构体记录下两个数的位置，但后来一像既然是相邻的那么只需要记录一个坐标的x或y即可，所以我选择了用数组直接存储。当x相等的时候存储下y的频数，在x不等的时候存下x的频数。完成记录后，对x，y的频数
进行桶排序，再将排序结果的索引存到新的数组，这时权重的排序就完毕了，然后只要新数组不为0的数从 0 到 k或l就是需要切割的行列。
题解：

#include <stdio.h>

#include <stdlib.h>

int min(int a, int b);

int main()

{

    int m = , n = , k = , l = , d = ;

    int x[] = {}, y[] = {};

    int col[] = {}, row[] = {};

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

    for (int i = ; 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 = ; i <= k; i++)

    {

//对y进行价值排序

        int max = -;

        int index = ;

        for (int j = ; j < m; j++)

        {

            if (y[j] > max)

            {

                max = y[j];

                index = j;

            }

        }

        y[index] = ;

        col[index]++;

    }

    for (int i = ; i <= l; i++)

    {//对y进行价值排序

        int max = -;

        int index = ;

        for (int j = ; j < n; j++)

        {

            if (x[j] > max)

            {

                max = x[j];

                index = j;

            }

        }

        x[index] = ;

        row[index]++;

    }

    for (int i = ; i < ; i++)

    {

        if (col[i])//遍历x

        {

            printf("%d ", i);

        }

    }

    printf("\n");

    for (int i = ; i< ;i++)

    {

        if (row[i])

        {

            printf("%d ", i);

        }

    }

    return ;

}

int min(int a, int b)

{

    return a < b ? a : b;

}

巴特西

洛谷训练场——简单模拟排座位（P1056）

题目描述

最新文章

热门文章

巴特西

洛谷训练场——简单模拟 排座位（P1056）

题目描述

最新文章

热门文章

洛谷训练场——简单模拟排座位（P1056）