-
YbtOJ「基础算法」第3章 二分算法
【例题1】数列分段
二分这个最大值，在 c h e c k check check 函数里面判断，如果该段的 s u m ≤ m i d sum \leq mid sum≤mid，不需要新的一段，否则需要，最后判断 c n t ≤ m cnt \leq m cnt≤m 是否成立。
#include#include #include #include #include #include #define re register #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 1e5+10; int n,m; int a[M]; int l,r,sum; inline bool check(int x){ int res = 0,cnt = 1; rep(i,1,n){ if(res + a[i] <= x) res += a[i]; else res = a[i],cnt++; } return cnt <= m; } signed main(){ n = read(),m = read(); rep(i,1,n) a[i] = read(),l = max(l,a[i]),r += a[i]; while(l < r){ int mid = (l+r)>>1; if(check(mid)) r = mid; else l = mid+1; } printf("%d\n",l); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
【例题2】防具布置
考虑二分一个位置，如果该位置和前面的防具恰好是奇数个，该位置 − 1 -1 −1 和前面的防具正好是偶数个，说明该位置有奇数个防具。最后输出类似于一个前缀和操作，该点的值减去前一个点的值。
#include#include #include #include #include #include #define re register #define int long long #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 2e5+10; int T,n,sum; struct node{ int s,e,d; node() { s = e = d = 0; } }a[M]; inline int check(int x){ int res = 0; rep(i,1,n) if(a[i].s <= x) res += (min(x,a[i].e) - a[i].s)/a[i].d + 1; return res; } inline void work(){ n = read(); sum = 0; rep(i,1,n){ scanf("%lld%lld%lld",&a[i].s,&a[i].e,&a[i].d); sum += (a[i].e-a[i].s)/a[i].d + 1; } if(sum % 2 == 0) { printf("There's no weakness.\n"); return; } int l = 0,r = 2147483647; while(l < r){ int mid = (l+r)>>1; if(check(mid) & 1) r = mid; else l = mid+1; } printf("%lld %lld\n",l,check(l) - check(l-1)); } signed main(){ T = read(); while(T--) work(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
【例题3】最大均值
要求平均数最大，我们二分这个平均数，并且把数组里的每一个值都减去这个平均数，问题就转化为了是否存在一个长度 ≥ L \geq L ≥L 的连续子段，子段和非负。
子串和转化为前缀和相减，可以用一个变量记录当前的最小值，每次与新的取值 s u m [ i − L ] sum[i-L] sum[i−L] 取 min \min min 即可， m i n n = min ( m i n n , s u m [ i − L ] ) minn = \min (minn,sum[i-L]) minn=min(minn,sum[i−L])， a n s = max ( a n s , s u m [ i ] − m i n n ) ans = \max (ans,sum[i] - minn) ans=max(ans,sum[i]−minn)。最后判断 a n s ≥ 0 ans \geq 0 ans≥0。
#include#include #include #include #include #include #define re register #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 1e5+10; double a[M],sum[M]; int n,m; double eps = 1e-6; inline bool check(double x){ rep(i,1,n) sum[i] = sum[i-1] + a[i] - x; double ans = -1e15,mi = 1e15; rep(i,m,n) mi = min(mi,sum[i-m]),ans = max(ans,sum[i]-mi); return ans >= 0; } signed main(){ n = read(),m = read(); rep(i,1,n) scanf("%lf",&a[i]); double l = -1e6,r = 1e6; while(l+eps < r){ double mid = (l+r) / 2; if(check(mid)) l = mid; else r = mid; } printf("%.0lf",l*1000); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
1. 1. 1. 喂养宠物
二分宠物的数量 x x x，每次排序，选前 x x x 小的加起来，判断是否 ≤ t o t f o o d \leq totfood ≤totfood
#include#include #include #include #include #include #define re register #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 1e5+10; int n,tot; int h[M],g[M],sum[M]; inline bool check(int x){ rep(i,1,n) sum[i] = h[i] + g[i]*(x-1); sort(sum+1,sum+n+1); int res = 0; rep(i,1,x) res += sum[i]; return res > tot; } signed main(){ n = read(),tot = read(); rep(i,1,n) h[i] = read(); rep(i,1,n) g[i] = read(); int l = 0,r = 50; while(l < r){ int mid = (l+r+1)>>1; if(check(mid)) r = mid - 1; else l = mid; } printf("%d\n",l); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
2. 2. 2. 最小时间
二分这个最小时间，把 k [ i ] k[i] k[i] 和 b [ i ] b[i] b[i] 带进去算，求前 m m m 大的，看最后答案是否 ≥ s \geq s ≥s。注意，这里求前 m m m 大，不能用 s o r t sort sort 会超时，可以用 n t h nth nth_ e l e m e n t element element 只排序前 m m m 大的后面的顺序不用管。
由于 n n n 个物品的价值总和在 t > 0 t > 0 t>0 时是单调的，我们只需要特判 t = 0 t = 0 t=0 即可。
#include#include #include #include #include #include #define re register #define int long long #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 1e6+10; int n,m,s; int k[M],b[M],sum[M]; inline bool cmp(int x,int y) { return x > y; } inline bool check(int x){ rep(i,1,n) sum[i] = k[i]*x + b[i]; nth_element(sum+1,sum+m,sum+n+1,greater<int>()); int res = 0; rep(i,1,m) if(sum[i] > 0 && (res += sum[i]) >= s) return 1; return res >= s; } signed main(){ n = read(),m = read(),s = read(); rep(i,1,n) k[i] = read(),b[i] = read(); int l = 0,r = 1e9; if(check(0)) { puts("0"); return 0; } while(l < r){ int mid = (l+r)>>1; if(check(mid)) r = mid; else l = mid + 1; } printf("%lld\n",l); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
3. 3. 3. 攻击法坛
我们二分 L L L 的最小值。
设 f [ i ] [ j ] f[i][j] f[i][j] 表示使用 i i i 次第一根法杖，使用 j j j 次第二根法杖最多可以覆盖到前几个法坛， p 1 [ i ] p1[i] p1[i] 表示在 a [ i ] a[i] a[i] 的位置使用第一根法杖最远可以覆盖到哪一个法坛， p 2 [ i ] p2[i] p2[i] 表示在 a [ i ] a[i] a[i] 的位置使用第二根法杖最远可以覆盖到哪一个法坛。
那么转移式为 f [ i ] [ j ] = max ( f [ i ] [ j ] , p 1 [ f [ i − 1 ] [ j ] + 1 ] ) f[i][j] = \max (f[i][j],p1[f[i-1][j]+1]) f[i][j]=max(f[i][j],p1[f[i−1][j]+1])， f [ i ] [ j ] = max ( f [ i ] [ j ] , p 2 [ f [ i ] [ j − 1 ] + 1 ] ) f[i][j] = \max (f[i][j],p2[f[i][j-1]+1]) f[i][j]=max(f[i][j],p2[f[i][j−1]+1]) 。
最后判断 f [ s 1 ] [ s 2 ] = = n f[s1][s2] == n f[s1][s2]==n 即可。
#include#include #include #include #include #include #define re register #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 2010; int n,s1,s2; int a[M],f[M][M],p1[M],p2[M]; inline bool check(int x){ memset(f,0,sizeof(f)); memset(p1,0,sizeof(p1)); memset(p2,0,sizeof(p2)); rep(i,1,n) rep(j,1,n){ if(a[j] - a[i] + 1 <= x) p1[i] = j; if(a[j] - a[i] + 1 <= 2*x) p2[i] = j; } p1[n+1] = p2[n+1] = n; rep(i,0,s1) rep(j,0,s2){ if(i > 0) f[i][j] = max(f[i][j],p1[f[i-1][j]+1]); if(j > 0) f[i][j] = max(f[i][j],p2[f[i][j-1]+1]); } return f[s1][s2] == n; } signed main(){ n = read(),s1 = read(),s2 = read(); rep(i,1,n) a[i] = read(); sort(a+1,a+n+1); if(s1 + s2 >= n) { printf("1\n"); return 0; } int l = 0,r = a[n] - a[1] + 1; while(l < r){ int mid = (l+r)>>1; if(check(mid)) r = mid; else l = mid+1; } printf("%d\n",l); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
4. 4. 4. 跳石头
也是一道很简单的二分，二分这个最大值，在 c h e c k check check 函数里判断需要取走的石头是否 ≤ m \leq m ≤m。
#include#include #include #include #include #include #define re register #define int long long #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 1e5+10; int L,n,m,ans; int a[M]; inline bool check(int x){ int pos = 0,cnt = 0; rep(i,1,n){ if(a[i] - pos < x) cnt++; else pos = a[i]; } return cnt <= m; } signed main(){ L = read(),n = read(),m = read(); rep(i,1,n) a[i] = read(); int l = 0,r = L; while(l < r){ int mid = (l+r+1)>>1; if(check(mid)) l = mid; else r = mid - 1; } printf("%lld\n",l); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
5. 5. 5. 飞离地球
二分 + + + s p f a spfa spfa
题目中规定不能在出发时间前到达目的地，也就是图中不能有负环。考虑二分速度调节器的增值，每一次用 s p f a spfa spfa 判断是否有负环，如果没有，看 n n n 是否能到，能到的话，答案记为 d i s [ n ] dis[n] dis[n]。
这里我们可以先处理出从 1 1 1 号点开始，可以走到那个点，并且这些点中哪些能到 n n n，可以减小我们 s p f a spfa spfa 所用时间。
#include#include #include #include #include #include #define re register #define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a) #define rep(a,b,c) for(re int a(b) ; a<=(c) ; ++a) using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int M = 1e5+10; const int inf = 0x3f3f3f3f; int T,n,m,cnt; int head[M],dis[M],vis[M],bo[M],tot[M],con[M]; struct edge{ int to,nxt,w; }e[M]; inline void add(int u,int v,int w){ e[++cnt].to = v; e[cnt].w = w; e[cnt].nxt = head[u]; head[u] = cnt; } inline void init(){ cnt = 0; memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); memset(vis,0,sizeof(vis)); memset(bo,0,sizeof(bo)); memset(con,1,sizeof(con)); } inline void dfs(int u){ bo[u] = 1; for(re int i(head[u]) ; i ; i=e[i].nxt) if(!bo[e[i].to]) dfs(e[i].to); } inline bool check(int x){ queue<int> q; memset(dis,0x3f3f3f3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(tot,0,sizeof(tot)); q.push(1); dis[1] = 0; vis[1] = 1; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 0; for(re int i(head[u]) ; i ; i=e[i].nxt){ int v = e[i].to,w = e[i].w; if(dis[v] > dis[u] + w + x && con[v]){ dis[v] = dis[u] + w + x; if(!vis[v]){ tot[v]++; q.push(v); vis[v] = 1; if(tot[v] >= n) return 0; } } } } return (dis[n] >= 0 && dis[n] != inf); } inline void work(){ init(); n = read(),m = read(); rep(i,1,m){ int u = read(),v = read(),w = read(); add(u,v,w); } dfs(1); rep(i,1,n) if(!bo[i]) con[i] = 0; rep(i,1,n){ if(!con[i]) continue; memset(bo,0,sizeof(bo)); dfs(i); if(!bo[n]) con[i] = 0; } int l = -1e6,r = 1e6,ans = -1; while(l <= r){ int mid = (l+r)>>1; if(check(mid)) ans = dis[n],r = mid-1; else l = mid + 1; } printf("%d\n",ans); } signed main(){ T = read(); while(T--) work(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
-
相关阅读:
手机视频怎么做成gif微信表情包？
【算法】滑动窗口题单——3.不定长滑动窗口（求最短/最小）⭐ 删除最短的子数组使剩余数组有序
策略模式，从防腐层改造聊到Nacos插件的应用
Android持久化技术，好内存不如烂存储
二叉搜索树的实现
11月26日：操作系统实验杂记 shmget（创建共享存储区） shmat（连接共享存储区） shmdt（断连共享存储区） shmctl（共享存储区控制）
二十二、SpringBoot + Jwt + Vue 权限管理系统 （3）
微信支付申请
[Linux]------初识多线程
python——使用API
- 原文地址：https://blog.csdn.net/glorious_dream/article/details/126462457
