BZOJ 2257 JSOI 2009 瓶子和燃料 數學

BZOJ 2257 JSOI 2009 瓶子和燃料 數學

題目大意：有一些固定容量的瓶子，你想從火星人用k個瓶子那裡拿到一些燃料，火星人只能從一個瓶子中轉移到另一個瓶子中，或者把一個瓶子中的燃料倒掉，或者將一個瓶子裝滿。每次火星人會給你他能給出的最少的燃料。問你能夠得到的最多的燃料。

思路：yy一下發現一些瓶子中能給出的最少的燃料就是這些瓶子容量的gcd，於是就把所有的瓶子容量的約數弄出來，找到最大的大於k個的就是答案。

CODE：

#include 
#include 
#include 
#include 
#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;
}