P1182 数列分段 Section II · znzryb
60pts TLE 可能是check函数复杂度太高了
```cpp
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10,maxans=1e13+7;
ll n,m,a[maxn];
inline bool check(ll x) {
ll s=1,subCnt=0;
while (s<=n) {
ll res=0,cnt=0;
for(ll i=s;i<=n;i++) {
if(res+a[i]>x)
break;
res+=a[i];
cnt+=1;
}
s+=cnt;
subCnt+=1;
}
if(subCnt<=m) {
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
ll l=1,r=maxans;
while(l<r) {
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
// 60pts https://www.luogu.com.cn/record/180491211
```
可以二分里套二分，当然那个二分我们就不写了，直接上stl
[P1182_2.in](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/ff1d1d99-76cf-491c-be4b-26290d697c94/P1182_2.in?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB466VXEF4VA4%2F20260211%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260211T073533Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEO7%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLXdlc3QtMiJGMEQCICla0WWYHDWgj4sPpSO616bma0VUM8p9FQGwSN2LhG9iAiAMooJckt8vdS8bxGh6aRlYkrlLuh3zkYu8He%2BSUuDDlSqIBAi3%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F8BEAAaDDYzNzQyMzE4MzgwNSIMuW%2B6R4xH57%2FidGtnKtwD7jYpxtfLVDKe4xoHIvvyHTfITQlPVCCAvHX5wvDEy7iQx8y2kJv%2BN4Dl7uBosbr9vDjZ2aLGmzj4SccnTQ9pHY79%2FeVolHpcZgXDNwuBZybBH5Rq6edhdW4oKV78gJYPQIpGNiE8mucSLup13NYnaG%2FwCtVEuOQ10YBgfC%2Bogxn8CpvfwBz62K9mBla7nrWRUitvZ0eYT4LsVMM%2FwT3grIlv%2BjlLSEMaq9cq7BWRO%2BFzHHOPN3ytu2j413qe6T%2BxRRNZ1HPzrLdHqvAXb6KdTdqnS4oHmtObez51hmTkjvDOnx5IuIZqmgTzJBOfVAa3hBJiRvY0NcyPwlfvOHm6xkklP84dhw6cRFH7BK37UniT5HaB9D4%2Bc0mlZZvvtRFDKqz4O0c1CaOoKfjBXeVMo0jIBHjNM1%2FmkoPrKzsX%2Bps5TMuCZBKlYdSNnIV4PZ9Ulig3aCyJpg0UtxKpCTqlwGMWDZPRta1QO9EEqyBcYXB75IrbDyWVU9vRamYuQVGphMuEs5Hcz32XwpvzkiiZ8YLLmhGS5yGXRen0mzu4ZzVNhcYCNO79QVMJXWOmBwamWBX9FJHuYxOW1lwnIEPM9EtmEUx8b6o3%2BhyUiUnWAd0zN2TmcxBZfkFnzUswlL2wzAY6pgG%2B6sTv89wF77lwxuzaXQsLBZ7xr7BccZbeM%2BfYUYN8tkJlwG61Miin90ae8xiwZ1nmGi2jmjpCRTTrGzhY2GqrpNHOYAmsWNU4Mdx0O%2B7kySpBSqmXleXJr2w9z6kWgCRsxyPf%2BER%2BKjpNnsFbLZ3ATihya9bNdNLTajG4%2Bl7d3dcnJthGuoMRy3GKu1R5cHa9t%2BlJBDlKn7IAzdDuZgPEWmc4WkZ%2B&X-Amz-Signature=bab216f9ac5be8a7a668d28cd9168da51b12564e19211e97b9a8131989ee4668&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
[P1182_2.out](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/a3ae9645-94d7-4f5a-a7f1-cccdfb015c3d/P1182_2.out?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB466VXEF4VA4%2F20260211%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260211T073533Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEO7%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLXdlc3QtMiJGMEQCICla0WWYHDWgj4sPpSO616bma0VUM8p9FQGwSN2LhG9iAiAMooJckt8vdS8bxGh6aRlYkrlLuh3zkYu8He%2BSUuDDlSqIBAi3%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F8BEAAaDDYzNzQyMzE4MzgwNSIMuW%2B6R4xH57%2FidGtnKtwD7jYpxtfLVDKe4xoHIvvyHTfITQlPVCCAvHX5wvDEy7iQx8y2kJv%2BN4Dl7uBosbr9vDjZ2aLGmzj4SccnTQ9pHY79%2FeVolHpcZgXDNwuBZybBH5Rq6edhdW4oKV78gJYPQIpGNiE8mucSLup13NYnaG%2FwCtVEuOQ10YBgfC%2Bogxn8CpvfwBz62K9mBla7nrWRUitvZ0eYT4LsVMM%2FwT3grIlv%2BjlLSEMaq9cq7BWRO%2BFzHHOPN3ytu2j413qe6T%2BxRRNZ1HPzrLdHqvAXb6KdTdqnS4oHmtObez51hmTkjvDOnx5IuIZqmgTzJBOfVAa3hBJiRvY0NcyPwlfvOHm6xkklP84dhw6cRFH7BK37UniT5HaB9D4%2Bc0mlZZvvtRFDKqz4O0c1CaOoKfjBXeVMo0jIBHjNM1%2FmkoPrKzsX%2Bps5TMuCZBKlYdSNnIV4PZ9Ulig3aCyJpg0UtxKpCTqlwGMWDZPRta1QO9EEqyBcYXB75IrbDyWVU9vRamYuQVGphMuEs5Hcz32XwpvzkiiZ8YLLmhGS5yGXRen0mzu4ZzVNhcYCNO79QVMJXWOmBwamWBX9FJHuYxOW1lwnIEPM9EtmEUx8b6o3%2BhyUiUnWAd0zN2TmcxBZfkFnzUswlL2wzAY6pgG%2B6sTv89wF77lwxuzaXQsLBZ7xr7BccZbeM%2BfYUYN8tkJlwG61Miin90ae8xiwZ1nmGi2jmjpCRTTrGzhY2GqrpNHOYAmsWNU4Mdx0O%2B7kySpBSqmXleXJr2w9z6kWgCRsxyPf%2BER%2BKjpNnsFbLZ3ATihya9bNdNLTajG4%2Bl7d3dcnJthGuoMRy3GKu1R5cHa9t%2BlJBDlKn7IAzdDuZgPEWmc4WkZ%2B&X-Amz-Signature=f0316103de75c69a72ee243434f8c16e82674ce04c5de9eea19961be5887af6d&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
不过我仔细分析了一下时间复杂度，以及这个样例(另一道题目[https://www.luogu.com.cn/problem/P2884](https://www.luogu.com.cn/problem/P2884))
```cpp
7 5
100
400
300
100
500
101
400
```
```cpp
500
```
会使上面这个程序死循环，让我确信不是check（）的问题
仔细分析过后，发现还是check（）的问题，check死循环了。
```cpp
while (s<=n) {
ll res=0,cnt=0;
for(ll i=s;i<=n;i++) {
if(res+a[i]>x) // 某些情况下，cnt走不到cnt+1，导致s停滞不前，导致死循环
break;
res+=a[i];
cnt+=1;
}
s+=cnt;
subCnt+=1;
}
```
解决起来倒也简单
ll l=maxa,r=maxans;
让左端点比数组中最大的元素大，就可以了，这样可以保证cnt的前进。
```cpp
// https://www.luogu.com.cn/problem/P2884
// https://www.luogu.com.cn/problem/P1182 双倍经验
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10,maxans=1e13+7;
ll n,m,a[maxn];
inline bool check(ll x) {
ll s=1,subCnt=0;
while (s<=n) {
ll res=0,cnt=0;
for(ll i=s;i<=n;i++) {
if(res+a[i]>x)
break;
res+=a[i];
cnt+=1;
}
s+=cnt;
subCnt+=1;
}
if(subCnt<=m) {
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
ll maxa=0;
for(int i=1;i<=n;i++) {
cin>>a[i],maxa=max(maxa,a[i]);
}
ll l=maxa,r=maxans;
while(l<r) {
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
// 60pts TLE https://www.luogu.com.cn/record/180491211
// 40pts TLE https://www.luogu.com.cn/record/180498527
// AC https://www.luogu.com.cn/record/180509878
// AC https://www.luogu.com.cn/record/180510298
```