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