求条

rainbow_MMM @ 2024-12-22 15:20:49

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005],n,m,l,r=100000000000;
bool chk(int x) {
    int ans=0;
    for(int i=1;i<=n;i++) {
        if(a[i]>=x) {
            ans+=a[i]/x;
        }
    }
    return ans>=m;
}
signed main() {
    int ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    while(l<=r) {
        int mid=(l+r)>>1;
        if(chk(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

by KellyH @ 2024-12-22 15:44:12

？

by KellyH @ 2024-12-22 15:45:07

我也不知道，先把我7月的代码放这

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long a[1000005];
bool z(long long x) 
{
    long long ans=0;
    for(int i=1;i<=n;i++) 
    {
        ans+=a[i]/x;
    }
    return ans>=k;
}
int main() 
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
    }
    long long l=0,r=100000005,mid;
    while(l+1<r) 
    {
        mid=(l+r)/2;
        if(z(mid)) 
        {
            l=mid;
        }
        else 
        {
            r=mid;
        }
    }
    cout<<l;
    return 0;
} 

by KellyH @ 2024-12-22 15:54:36

@rainbow_MMM qp

by xuzifan123 @ 2024-12-22 16:38:14

分析题目 看起来有点复杂，其实很简单。

时间复杂度为O（log2n）

只要把木材每段长度二分就行了。

首先，还是两个指针l和r。

由于我们不知道长度的范围，这里就用一个大数据来代替。

long long s,l=0,r=0x7fffffff;

输入

cin>>n>>k;

for(int i=1;i<=n;i++)cin>>a[i];

开始二分。

我们还是区中点，找范围。

但这里判断方式不一样，我们为了要确保段数要符合条件，我们还需要一个判断。

判断方式就是累加段数，看看有没有小于段数，如果小就将左指针向右移至当前中点。

如果大于等于段数，就将右指针向左移至当前中点

int js(int x){

    register int i;
    t=0;
    for(i=1;i<=n;i++){
        t+=a[i]/x;
        if(t>=k) return 1;
    }
    return 0;
} 

while(l+1<r)
    {

        m=l+(r-l)/2;
        if(js(m)==1) l=m;
        else r=m;
    }

最后输出

cout<<l;

贴代码：

#include<bits/stdc++.h>
using namespace std;
long long a[100001],t=0,k,m,n;
int js(int x){
    register int i;
    t=0;
    for(i=1;i<=n;i++){
        t+=a[i]/x;
        if(t>=k) return 1;
    }
    return 0;
}
int main(){
    long long s,l=0,r=0x7fffffff;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(l+1<r){
        m=l+(r-l)/2;
        if(js(m)==1) l=m;
        else r=m;
    }
    cout<<l;
    return 0;
}