题目大意
有 N个瓶子(1<=N<=1000)中拿出K个用来装燃料, 火星人可以
1、将某个瓶子装满燃料;
2、将某个瓶子中的燃料全部倒回燃料库;
3、将燃料从瓶子a倒向瓶子b,直到瓶子b满或者瓶子a空。
K个瓶子内必须有燃料, 火星人会尽可能减少燃料总量, 问能得到最多燃料的瓶子组合。
解题报告
可以发现一个规律
两个瓶子a,b能达到不为0的最小容量为gcd(a,b)
解释: 瓶子见相互倾倒类似于gcd的辗转相除,只不过把取模运算换成了从A倒满B然后把B倒空 (好像没说清楚。。算了请自行脑补吧。。)
然后既然可以达到这么一个体积,那么可以把a,b两个瓶子看为一个体积为gcd(a,b)的瓶子
那么问题就变成了一个相同的子问题,就可以知道答案是把所有N个数中选K个数使得这K个数的gcd最大。
然后解法非常暴力。。每个数字的因子最多有2*sqrt(a)个,(其实数量是远远小于这个数的),可以搞出所有数的因子然后排个序统计出现次数大于等于K的最大因子就是答案。
但是Hineven很懒,写了个map代替排序……
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
std :: map<int, int> table;
int ans = 1;
int N, K;
void div(int num) {
for(int i = 1; i*i<=num; i++)
if(num%i == 0) {
table[i]++;
if(table[i] >= K) ans = std :: max(ans, i);
table[num/i]++;
if(table[num/i] >= K) ans = std :: max(ans, num/i);
}
}
int main () {
scanf("%d%d", &N, &K);
for(int i = 1; i<=N; i++) {
int a;
scanf("%d", &a);
div(a);
}
printf("%d\n", ans);
}
Join the discussion