2023牛客OI赛前集训营-提高组（第三场）C.分糖果

本文主要是介绍2023牛客OI赛前集训营-提高组（第三场）C.分糖果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2023牛客OI赛前集训营-提高组（第三场）C.分糖果

C-分糖果_2023牛客OI赛前集训营-提高组（第三场） (nowcoder.com)

题目大意

求前 $i(i\in [1,n])$ 个数分成 $k$ 个连续的区间，每一个区间和的最大值最小是多少。

$T$ 组数据

对于 $30pts$ ，$1\le n\le 100,1\le k\le n$

另外 $20pts$ ，$1\le n\le 10^4,k=1$

另外 $50pts$，$1\le n\le 10^5,1\le k\le n$

对于全部数据有 $T\le 3,|a_i|\le 10^9,1\le n\le 10^5$

做法

考试忘记加换行，$50pts\to 0$

对于 $30pts$

直接二分答案 + $dp$ ， $O(n^2)$ 判断能不能分成大于等于 $k$ 块的和满足假设。

对于 $20pts$

直接前缀和乱搞

$50pts$ 代码

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 1e5 + 5 , M = 1e5 + 5;
const LL inf = 1e14 + 5;
int n , k;
LL a[M] , f[M] , s[M] , ans;
bool ck (LL x) {int l = 1;fu (i , 1 , n) f[i] = 0;fu (i , 1 , n) {if (i == 1) {f[i] = (s[1] <= x);}else {fu (j , 1 , i) {if (s[i] - s[j - 1] <= x && (f[j - 1] || j == 1)) f[i] = max (f[i] , f[j - 1] + 1);}}if (f[i] >= k) return 1;}return 0;
}
LL fans (LL l , LL r) {if (l == r) {return ck (l) ? l : inf;}LL mid = l + r >> 1;if (ck (mid)) return min (fans (l , mid) , mid);else return min (inf , fans (mid + 1 , r));
}
int main () {// freopen ("candy2.in" , "r" , stdin);int T; scanf ("%d" , &T);while (T --) {scanf ("%d%d" , &n , &k);fu (i , 1 , n) scanf ("%lld" , &a[i]) , s[i] = 0;fu (i , 1 , n) s[i] = s[i - 1] + a[i];if (k == 1) {ans = inf;fu (i , 1 , n) ans = min (ans , s[i]);printf ("%lld\n" , ans);continue;}printf ("%lld\n" , fans (-inf , inf));}
}

对于 $100pts$

权值线段树 + 离散化

我们发现上面的 $dp$ 转移太慢了

$s$ 数组表示前缀和 ，当前二分答案为 $x$

对于 $i\in [1,n]$ 我们只用找到 $j\in [1,i]$ 满足 $s[i]-s[j]\le x$ 即 $s[i]-x\le s[j]$ 时的最大值 $+1$

即
$$f[i]=MA{X}_{j=1}^{i}f[j]+1(s[i]-x\le s[j])$$
用权值线段树维护就好了。

初始化 $f[0]=0$

每次把 $f[i]$ 插入权值线段树中

因为总和太大了，所以还要把 $s[i]$ 和 $s[i]-x$ 拿出来离散化（还有 $0$） ，动态开点。

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 4e7 + 5 , M = 2e5 + 5;
const LL inf = 1e9 * 1e6;
const int inff = 1e9 + 5;
int n , k , cnt , mp[M];
LL a[M] , f[M] , s[M] , ans , ss[M << 1];
struct Tr {int v , lp , rp;
} tr[N];
void glp (int p) {if (!tr[p].lp) {tr[p].lp = ++cnt;tr[cnt].v = -inff;}
}
void grp (int p) {if (!tr[p].rp) {tr[p].rp = ++cnt;tr[cnt].v = -inff;}
}
void change (int p , LL l , LL r , int x , int val) {if (l == r) tr[p].v = max (tr[p].v , val);else {int mid = l + r >> 1;if (x <= mid) {glp (p);change (tr[p].lp , l , mid , x , val);}else {grp (p);change (tr[p].rp , mid + 1 , r , x , val);}tr[p].v = max (tr[tr[p].lp].v , tr[tr[p].rp].v);}
}
int query (int p , LL l , LL r , LL L , LL R) {if (L <= l && R >= r) return tr[p].v;else {int mid = l + r >> 1 , ans1 = -inff , ans2 = -inff;if (L <= mid && tr[p].lp) ans1 = query (tr[p].lp , l , mid , L , R);if (R > mid && tr[p].rp) ans2 = query (tr[p].rp , mid + 1 , r , L , R);return max (ans1 , ans2);}
}
void cl (int p) { tr[p].lp = tr[p].rp = 0 , tr[p].v = -inff; }
void clear (int p , LL l , LL r) {if (l == r) {cl (p);return;}int mid = l + r >> 1;if (tr[p].lp) clear (tr[p].lp , l , mid);if (tr[p].rp)clear (tr[p].rp , mid + 1 , r);cl (p);
} 
bool ck (LL x) {int s1 = 1;ss[1] = 0;fu (i , 1 , n) {ss[++s1] = s[i];ss[++s1] = s[i] - x;}sort (ss + 1 , ss + s1 + 1);int m = unique (ss + 1 , ss + s1 + 1) - ss - 1;clear (1 , -M , M);tr[0].v = -M;cnt = 1;int y = lower_bound(ss + 1 , ss + s1 + 1 , 0) - ss;change (1 , -M , M , y , 0);fu (i , 1 , n) {y = lower_bound(ss + 1 , ss + s1 + 1 , s[i] - x) - ss;f[i] = query (1 , -M , M , y , M) + 1;y = lower_bound(ss + 1 , ss + s1 + 1 , s[i]) - ss;change (1 , -M , M , y , f[i]);if (f[i] >= k) return 1;}return 0;
}
LL fans (LL l , LL r) {if (l == r) return ck (l) ? l : inf;else {LL mid = l + r >> 1;if (ck (mid))  {return min (fans (l , mid) , mid);}else {return fans (mid + 1 , r);}}
}
int main () {// freopen ("candy2.in" , "r" , stdin);int T; scanf ("%d" , &T);while (T --) {scanf ("%d%d" , &n , &k);fu (i , 1 , n) scanf ("%lld" , &a[i]) , s[i] = 0;fu (i , 1 , n) s[i] = s[i - 1] + a[i];printf ("%lld\n" , fans (-inf , inf));}
}

这篇关于2023牛客OI赛前集训营-提高组（第三场）C.分糖果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---