欢乐赛#67 T6 题解

题目大意

@skirmish 有 $n$ 根绳子，第 $i$ 根长度为 $a_i$，他可以把 $n$ 根绳子中的每一根绳子剪成若干段，每段长度都必须是同一个正整数 $L$，剩余部分会被丢弃。

@skirmish 希望得到至少 $k$ 段长度为 $L$ 的绳段，请你求出满足条件的最大的 $L$。无解则输出0。

解法一

求最大值，又不能直接求，上二分答案！

左边界 $l\gets1$，右边界 $r\gets\max^{n}_{i=1}a_i$。

check 函数也就很好写了，求出每一根绳子的段数之和，判断其是否至少为 $k$。

Code 1

令 $m=\max^{n}_{i=1}a_i$，则时间复杂度为：$\text O(n\log m)$。

用古诗文形容一下此解法？

若止印三二本，未为简易；若印数十百千本，则极为神速。

但官方的数据貌似是三二本（？）。

#include <bits/stdc++.h>
using namespace std;
int n,k,l=1,r=1005,ans;//如果无解 ans 不会更新，即 0
int a[105];
bool check(int l){//判断此时的 L(mid)是否满足条件
    int res=0;
    for (int i=1;i<=n;i++){
        res+=a[i]/l;
    }
    return res>=k;
}
int main(){
	cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        r=max(r,a[i]);
    }
    while (l<=r){//二分答案
        int mid=(l+r)/2;
        if (check(mid)){
            l=mid+1;
            ans=mid;//记录答案
        }
        else {
            r=mid-1;
        }
    }
    cout<<ans;
	return 0;
}

解法二

不能直接求，那为什么不来暴力枚举呢？

直接从右边界 $\max^{n}_{i=1}a_i$ 向 $1$ 枚举，找到答案就停。

check和上面一样。

Code 2

令 $m=\max^{n}_{i=1}a_i$，则时间复杂度为：$\text O(nm)$。

#include <bits/stdc++.h>
using namespace std;
int n,k,ans;
int a[105];
bool check(int l){
    int res=0;
    for (int i=1;i<=n;i++){
        res+=a[i]/l;
    }
    return (res>=k);
}
int main(){
	cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        ans=max(ans,a[i]);
    }
    for (;ans>=1;ans--){//只有这部分有明显区别
        if (check(ans)){
            cout<<ans;
            return 0;
        }
    }
    cout<<0;//没有找到答案，无解
	return 0;
}