描述 Description
农场中, 由于奶牛数量的迅速增长, 通往奶牛宿舍的道路也出现了严重的交通拥堵问题. FJ 打算找出最忙碌的道路来重点整治. 这个牧区包括一个由 M (1 ≤ M ≤ 50,000)条单行道路 (有向) 组成的网络, 以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为 1..N), 每一条道路连接两个不同的交叉路口. 奶牛宿舍位于第 N 个路口. 每一条道路都由编号较小的路口通向编号较大的路口. 这样就可以避免网络中出现环. 显而易见, 所有道路都通向奶牛宿舍. 而两个交叉路口可能由不止一条边连接. 在准备睡觉的时候, 所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍, 奶牛只会在入度为 0 的路口, 且所有入度为 0 的路口都会有奶牛. 帮助 FJ 找出最忙碌的道路, 即计算所有路径中通过某条道路的最大次数. 答案保证可以用 32 位整数存储.
输入格式 InputFormat
第一行：两个用空格隔开的整数：N 和 M.
第 2..N+1 行：第 i+1 行包含 FJ 在他的第 i 个工作日的花费.
输出格式 OutputFormat
第一行：能够维持每个月农场正常运转的钱数
样例输入 SampleInput
10 3
1
1
1
10000
1
1
1
1
1
1
样例输出 SampleOutput
10000
来源 Source
Silver
代码 Code
二分答案，判断可行性。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/27.11;
int a[100005];
int i,j,t,n,m,l,r,k,z,y,x,ans;
bool can(int s)
{
int i,j,t,z,y,x;
x=0;z=1;
for (i=1;i<=n;i++)
{
if (a[i]>s) return false;
if (x+a[i]<=s)
{
x+=a[i];
continue;
}
z++;
x=a[i];
if (z>m) return false;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
l=r=0;
for (i=1;i<=n;i++) scanf("%d",&a[i]),l=max(l,a[i]),r+=a[i];
ans=inf;
while (l<r)
{
t=(l+r)>>1;
if (can(t)) ans=min(ans,t),r=t;
else l=t+1;
}
printf("%d\n",ans);
return 0;
}