HDU 6195 2017沈阳网络赛公式

2024-08-29 14:17:40

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6195

题意：有M个格子，有K个物品。我们希望在格子与物品之间连数量尽可能少的边，使得——不论是选出M个格子中的哪K个，都可以与K个物品恰好一一匹配。

解法：从样例猜出答案应该是K*(M-K+1)。从这个样例可以找到合法的解决方案。每个物品，都要向（M - K + 1）个格子连去一条边，我们会丢弃M - K个格子，但总会剩下一个格子是与这个物品连边的。

我们强制这样连边1 -> [1, M - K + 1] 2 -> [2, 1 + M - K + 1] 3 -> [3, 2 + M - K + 1] K -> [K, M] 这样不论选哪些格子，第一个物品总是能匹配第一个格子，第二个物品总是能匹配第二个格子…… 所以总能合法匹配！

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

    LL M,K;

    while(~scanf("%lld %lld", &M,&K))

    {

        LL ans = K*(M-K+1);

        printf("%lld\n", ans);

    }

    return 0;

}

最新文章

热门文章