526互联

Atcoder beginner constest319 Minimum Width

发布时间 2023-10-14 11:57:47作者: 只会做红色题

因为要求窗口的最小宽度，当宽度为w时满足条件，那么宽度为w+1时也满足条件，有此可见是有单调性的，那么可以用二分搜的方法，且此题目一定有解。因为M最大为2乘以10的5次方，Li最大为10的9次方，所以宽度最大为2乘以10的14次方，单词每次间隔1，所以这里设成10的17次方。之后就是套二分模板解暴力模拟就可以了。

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N],m,n;

bool check(ll x)
{
  ll sum=0,cnt=1; //至少为一行
  for(int i=0;i<n;++i)
  {
    if(a[i]>x) return 0; //如果字母长度大于宽度结束，宽度扩大。
    if(sum+a[i]<=x) sum+=a[i]; //字母长度小于宽度就累加，在宽度范围内就累加。
    else 
    {
      sum=a[i]; // 超出宽度就更新sum的值，跳到下一行
      cnt++;
    }
    sum++; // 每个单词相隔1
  }
  return cnt<=m; 判断宽度是否增大还是减小。
}

signed main()
{
  scanf("%lld %lld",&n,&m);
  for(int i=0;i<n;++i) scanf("%lld",&a[i]);
  ll l=1,r=1e17;    //右边界范围弄大一点，其实3乘以10的14次方足够了
  while(l<r)  //二分模板
  {
    ll mid=(l+r)>>1;
    if(check(mid)) r=mid; //不断二分，直到l等于r结束。
    else l=mid+1;
  }
  printf("%lld\n",l);
  return 0;
}