中国企业集成网网址电子商务_网址大全123下载apk_seo行业岗位有哪些_google搜索下载

标签：前缀和+二分 

传送门 0深秋的苹果【算法赛】 - 蓝桥云课

洛谷题目我也有详细讲解 洛谷 P1182 数列分段 Section II 二分详细讲解全新版本_洛谷b38408二级讲解-CSDN博客

 

正如题目所言,这是一道洛谷数列分段 P1182 数列分段 Section II - 洛谷 的变形，只不过是将区间求和转为区间内数两两相乘的总和，这里的check区间两两数乘积的和 的做法利用的前缀和的思想,这个前缀和的思想值得学一下

附上草图一张

const int N = 2e5 + 10;int n,m;
LL a[N],s[N];bool check(LL mid)
{LL cnt = 0,sum = 0,l = 1;for (int i = 1;i <= n;i ++){LL t = a[i] * (s[i - 1] - s[l - 1]);if (sum + t <= mid) sum += t;else {l = i,sum = 0;cnt ++;}}cnt ++;if (sum > mid) return false;return cnt <= m;
}void solve()
{cin >> n >> m;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i <= n;i ++) s[i] = s[i - 1] + a[i];LL l = -1,r = 2e18;while(l + 1 != r){LL mid = l + r >> 1;if (check(mid)) r = mid;else l = mid;}if (check(l)) cout << l << endl;else cout << r << endl;
}