BZOJ 2257 [Jsoi2009]瓶子和燃料
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2257
题意:给定n个瓶子的容量,选出其中k个,最大化k个瓶子之间无度量所能表达的最小体积。
题解:
考虑两个瓶子(容量为a
和b
),互相倒来倒去能表示的体积都是以两个瓶子容量生成的值ax+by
,而(a,b)|ax+by
,所以最小体积就是(a,b)
,推广到k个瓶子,题目即最大化k
个瓶子的最大公因数。
考虑将每个数分解因数,找最大且出现至少k
次的因数即可。
不考虑map的时间复杂度为
代码:
#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
map<int, int> cnt;
int n, k, x, i;
int main()
{
scanf("%d%d", &n, &k);
while(n--)
{
scanf("%d", &x);
for(i = 1; i * i < x; ++i)
if(x % i == 0) ++cnt[i], ++cnt[x / i];
if(i * i == x) ++cnt[i];
}
map<int, int>::iterator it = cnt.end(), jt = cnt.begin();
for(--it, --jt; it != jt; --it)
if(it -> second >= k)
{
printf("%d\n", it -> first);
break;
}
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。