题目大意:有一些固定容量的瓶子,你想从火星人用k个瓶子那里拿到一些燃料,火星人只能从一个瓶子中转移到另一个瓶子中,或者把一个瓶子中的燃料倒掉,或者将一个瓶子装满。每次火星人会给你他能给出的最少的燃料。问你能够得到的最多的燃料。
思路:yy一下发现一些瓶子中能给出的最少的燃料就是这些瓶子容量的gcd,于是就把所有的瓶子容量的约数弄出来,找到最大的大于k个的就是答案。
CODE:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10000010
using namespace std;
int cnt,k;
int arr[MAX],total;
inline void Work(int x)
{
for(int i = 1;; ++i) {
if(i * i >= x) {
arr[++total] = i;
return ;
}
if(x % i == 0)
arr[++total] = i,arr[++total] = x / i;
}
}
int main()
{
cin >> cnt >> k;
for(int x,i = 1; i <= cnt; ++i) {
scanf("%d",&x);
Work(x);
}
sort(arr + 1,arr + total + 1);
int temp = 1;
for(int i = total - 1; i; --i) {
if(arr[i] == arr[i + 1]) ++temp;
else {
if(temp >= k) {
cout << arr[i + 1] << endl;
return 0;
}
temp = 1;
}
}
return 0;
}