P1182 数列分段 Section II（尚有疑问）

青旅半醒 2022-11-13 12:25 6阅读 0赞

[题解来自这里][Link 1]

[题目][Link 2]

问题是：我怎么知道mid该如何确定?  
version 1.0  
`int mid =( sum[1]+sum[n]) >> 1;`  
version 2.0  
mid 属于\[max(a\[i\]), sum\]

离谱，万一选了一个没有对应区间和的咋办？

version 1.0

#include<bits/stdc++.h>
    #define ll long long
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define inf 2147483647
    const int mod=1e9+7;
    const int maxn=1e5+7;
    using namespace std;
    int sum[maxn], n, m;
    
    inline bool check(int mid)
    { 
        int cnt = m, tmp = 1, pos = 0;
        while(cnt--){ 
            while(sum[tmp]-sum[pos] <= mid && tmp <= n) tmp++;
            pos = --tmp;
            if(pos==n) return true;
        }
        return false;
    }
    
    int main()
    { 
        ios;
        cin >> n >> m;
        rep(i,1,n){ 
            int temp;
            cin >> temp;
            sum[i] = temp + sum[i-1]; // 前缀和
        }
        
        int l = sum[1], r = sum[n], ans;
        while(l <= r){ 
            int mid = (l + r) >> 1;
            if(check(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans;
        return 0;
    }

version 2.0

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N = 100010;
    int n,m,a[N];
    bool check(int k)
    { 
    	int cur=0,ans=1;
    	for(int i=1;i<=n;i++)
    	{ 
    		if(cur+a[i]>k)
    		{ 
    			cur=0;
    			ans++;
    		}
    		cur+=a[i];
    	}
    	return ans<=m;
    }
    int main()
    { 
    	scanf("%d%d",&n,&m);
    	int l=0,r=0,ans=0;
    	for(int i=1;i<=n;i++)
    	{ 
    		scanf("%d",&a[i]);
    		r+=a[i];
    		l=max(l,a[i]);
    	}
    	while(l<=r)
    	{ 
    		int mid=(l+r)>>1;
    		if(check(mid))
    		{ 
    			ans=mid;
    			r=mid-1;
    		}
    		else l=mid+1;
    	}
    	printf("%d\n",ans);
    	return 0;
    }

在version 2.0中，二分也可以使用倍增的思想

int p=1,j=r;
    	while(p)
    	{ 
    		int k=j-p+1;
    		if(k>=l&&check(k))
    		{ 
    			ans=k;
    			j-=p;
    			p*=2;
    		}
    		else p/=2;
    	}

[Link 1]: https://www.luogu.com.cn/problem/solution/P1182
[Link 2]: https://www.luogu.com.cn/problem/P1182