Skip to content

14035: 【原4035】泰先生的时光机

题目

题目描述

author: SupremeT 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4035

Description

泰先生是新任时空管理局的局长,他将参与时光机的设计工作。 时光机的建造需要昂贵的陨金,现在时空管理局中的陨金数量仅仅够建造M台时光机(每台时光机搭载人数相同)。 泰先生管理的星系中,总共有N个城镇,每个城镇中都有一定数量的人想要进行时光旅行。 请你帮帮泰先生,每台时光机的搭载量至少为多少,才能满足所有人的时光旅行愿望呢

注意:一台时光机不能被来自不同城镇的乘客共用!

Input Format

第一行,两个整数,分别为N,M(1 < N < 500000, N < M < 2000000) 从第二行起,N个整数,表示每个城镇中想要进行时光旅行的人数a[i](0 < a[i] < 500000)

Output Format

一个整数,时光机的最小搭载量

Sample Input

2 7
200000
500000

Sample Output

100000

数据范围

对于30%的数据,1 < N < 10, N < M < 40
对于70%的数据,1 < N < 1000, N < M < 4000
对于100%的数据,1 < N < 500000, N < M < 2000000

FineArtz's solution

/* 泰先生的时光机 */
#include <iostream>
using namespace std;

int n, m;
int a[500005] = {0};

long long check(long long l, long long r){
    if (l >= r) return l;
    long long mid = (l + r) / 2;
    int cnt = 0;
    bool flag = true;
    for (int i = 1; i <= n; ++i){
        cnt += a[i] / mid;
        if (a[i] % mid != 0) ++cnt;
        if (cnt > m) {
            return check(mid + 1, r);
            flag = false;
            break;
        }
    }
    if (flag) return check(l, mid);
}

int main(){
    cin >> n >> m;
    long long sum = 0;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        sum += a[i];
    }
    long long l = sum / m, r = sum;
    cout << check(l, r) << endl;
    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
int sum,n,m,a[600000],l,r,mid,ans=500000;
bool test(int x){
    sum=0;
    for (int i=0;i<n;++i)
        sum+=(a[i]-1)/x+1;
    return sum<=m;
}
int main() {
    cin>>n>>m;
    for (int i=0;i<n;++i) cin>>a[i];
    l=0;
    r=500000;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (test(mid)){
            if (mid<ans) ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<ans;
    return 0;
}