薛猫猫杯程序设计网络赛___球球大作战 —— 二分

本文主要是介绍薛猫猫杯程序设计网络赛___球球大作战 —— 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    给出一个长为 $n$ 的序列，相邻的元素可以合并，最多合并 $m$ 次，求合并后这个序列中最小值最大为多少？？？

解题思路：

    思路很清晰，每次合并一定是找最小值合并，关键是dp肯定是超时，那么就利用二分的思想
    先假设一个合并完成之后的最小值出来，看通过 $m$ 次合并能不能使得序列最小值等于这个虚拟最小值，若大于这个最小值，则增大这个虚拟最小值，反之则减小虚拟最小值，继而转化为了二分

代码思路：

    判断序列最小值的时候，因为我们只要求这个序列通过合并后能大于这个最小值，所以只需要遍历一遍，一旦发现当前元素小于最小值，则往后合并，也就满足了题意
    同时，二分的上限不是序列最大值，而是序列的总和，因为 $m$ 可能等于 $n-1$

核心：二分最小值，由数据范围想到$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
ll n, m, sum, ans, x[N], a[N];bool find(ll k){ll cnt = 0;for(int i=1; i<=n; i++) a[i] = x[i];for(int i=1; i<=n; i++){if(a[i]<k){a[i+1] += a[i];cnt++;}}return cnt<=m;
}int main(){int T;scanf("%d", &T);while(T--){sum = ans = 0;scanf("%lld%lld", &n, &m);for(int i=1; i<=n; i++) scanf("%lld", x+i), sum += x[i];int l = 0, r = sum, mid;while(l<=r){mid = (l + r)/2;if(find(mid)){ans = mid;l = mid + 1;}else r = mid - 1;}printf("%lld\n", ans);}	
}

这篇关于薛猫猫杯程序设计网络赛___球球大作战 —— 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---