程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 2257 JSOI 2009 瓶子和燃料 數學

BZOJ 2257 JSOI 2009 瓶子和燃料 數學

編輯:C++入門知識

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


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved