列表

详情

NC51315. Steady Cow Assignment

描述

Farmer John's cows each reside in one of barns which, of course, have limited capacity. Some cows really like their current barn, and some are not so happy.
FJ would like to rearrange the cows such that the cows are as equally happy as possible, even if that means all the cows hate their assigned barn.
Each cow gives FJ the order in which she prefers the barns. A cow's happiness with a particular assignment is her ranking of her barn. Your job is to find an assignment of cows to barns such that no barn's capacity is exceeded and the size of the range (i.e., one more than the positive difference between the the highest-ranked barn chosen and that lowest-ranked barn chosen) of barn rankings the cows give their assigned barns is as small as possible.

输入描述

Line 1: Two space-separated integers, N and B
Lines 2..N+1: Each line contains B space-separated integers which are exactly 1..B sorted into some order. The first integer on line i+1 is the number of the cow i's top-choice barn, the second integer on that line is the number of the i'th cow's second-choice barn, and so on.
Line N+2: B space-separated integers, respectively the capacity of the first barn, then the capacity of the second, and so on. The sum of these numbers is guaranteed to be at least N.

输出描述

Line 1: One integer, the size of the minumum range of barn rankings the cows give their assigned barns, including the endpoints.

示例1

输入: 

6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2

输出: 

2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 90ms, 内存消耗: 548K, 提交时间: 2021-08-17 18:07:19 

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 1010;
int maps[maxn][22], vis[22], used[22][maxn];
int link[22], limit[22], n, m, s, e, mid;
bool Find (int u)
{
    for (int i=1; i<=m; i++)
    {//多重匹配
        if (!vis[i] && maps[u][i]<e && s<=maps[u][i])
        {
            vis[i] = 1;
            if (link[i] < limit[i])
            {//i棚子未满
                used[i][link[i] ++] = u;
                return true;
            }
            for (int j=0; j<limit[i]; j++)//i棚子已满，寻找增广路
                if (Find(used[i][j]))
                {
                    used[i][j] = u;
                    return true;
                }
        }
    }
    return false;
}
bool hungry ()
{
    for (s=1; s<=m+1-mid; s++)
    {//枚举区间起点与终点
        int ans = 0;
        e = s + mid;
        memset (link, 0, sizeof(link));
        for (int i=1; i<=n; i++)
        {
            memset (vis, 0, sizeof(vis));
            if (Find (i))
                ans ++;
        }
        if (ans == n)
            return true;
    }
    return false;
}
int main ()
{
    while (scanf ("%d %d", &n, &m) != EOF)
    {
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
            {
                scanf ("%d", &mid);
                maps[i][mid] = j;
            }
        for (int i=1; i<=m; i++)
            scanf ("%d", &limit[i]);
        int left = 1, right = m, ans = 0;
        while (left<=right)
        {//二分枚举区间
            mid = (right+left)/2;
            if (hungry())
                {
                    ans = mid;
                    right = mid - 1 ;
                }
            else
                left = mid + 1 ;
        }
        printf ("%d\n", ans);
    }
    return 0;
}

上一题

© 2024 nowcoder.com