hdu6195 cable cable cable 找规律推公式
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=6195
题意：
有n个显示屏和k个不同信号源，在显示屏和信号源之间连线，一个显示屏若和多个信号源连接，可以显示任意一个信号，使得任意选出k个显示屏，可以使这k个显示屏的信号都不同，问最小需要的连线
思路：
首先选出k个显示屏，这k个显示屏每一个都连接一个不同的信号源，剩余的n−k个显示屏每一个都连接所有的信号源，这样构造出来的满足题意且是最少的，那么公式就是k+(n−k)∗k
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10, INF = 0x3f3f3f3f;
int main()
{
int n, k;
while(~ scanf("%d%d", &n, &k)) printf("%lld\n", 1LL * (n-k) * k + k);
return 0;
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |