P1182 数列分段 Section II
再一次对位单杀18年的我
\(2018 0pts\)
#include<cctype>
#include<cstdio>
#include<algorithm>
using std::sort;
int n,a[100010],QZ_sum[100010],m,ans=-0x7fffffff,minn=0x7fffffff;
inline int read(int &x){
x=0;
char ch=0;
bool sign=false;
while(!isdigit(ch)){sign|=(ch=='-');ch=getchar();}
while(isdigit(ch)) {x=x*10+(ch^48);ch=getchar();}
x=sign?-x:x;
}
inline int max(int a,int b){
return a>b?a:b;
}
inline int min(int a,int b){
return a<b?a:b;
}
inline void out(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)out(x/10);
putchar(x%10+'0');
}
inline void dfs(int i,int num,int sum,int ans){
if(i==n+1){
if(num>=m){
minn=min(minn,ans);
}
return ;
}
int cmp=max(ans,sum);
dfs(i+1,num+1,a[i+1],cmp);
dfs(i+1,num,sum+a[i+1],ans);
}
int main(){
read(n);read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
dfs(1,1,a[1],-0x7fffffff);
dfs(1,0,a[1],-0x7fffffff);
out(minn);
return 0;
}
最近复习二分，这题其实就是套板子，check函数也还算好实现，但是只拿了80pts。
\(2023 80pts\)
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll l, r, mid;
int n, m;
int a[100010];
bool check(int x)
{
int temp = 0, cnt = 0;
for (int i = 1; i <= n; i++)
{
if (temp + a[i] > x)
{
cnt++;
temp = a[i];
}
else
{
temp += a[i];
}
}
cnt = (temp) ? cnt + 1 : cnt;
return temp <= x && cnt <= m;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
l = 1, r = 1e9;
int ans = 0;
while(l <= r)
{
mid = l + ((r - l) >> 1);
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
printf("%d", ans);
return 0;
}
百思不得其解，看了讨论区很多人和我一样，然后发现了问题。
\(l\)左区间不能从\(1\)或者\(0\)开始，因为二分答案查找的是数列分段和的最小值，而左区间从零开始则排除不了\(mid\)小于数列其中一个数的情况，而这种情况显然是不成立的，我的算法中也没有加入特判，因此最优解就是直接把\(l\)左区间设成数列中的最大值，防止出现数列和最大值比数列中其中一个数还小的情况。