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

题目描述

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

Sample Input

``````2 7
200000
500000
``````

Sample Output

``````100000
``````

数据范围

``````对于30%的数据，1 < N < 10, N < M < 40

``````

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