所謂wqs，就是windwhisper說：“qs”

（逃）

解析

很神奇的科技。
四兩撥千斤的解決一些本來可能不太好解決的問題。

經典模型：有若干個物品，要求選出 $m$ 個，選的時候帶有限制，求最優的方案。

這個正常 dp 常常需要加一維記錄個數，復雜度 $O(n^2)$ 難以通過。
設 $f(x)$ 表示選 $x$ 個元素的最優答案，那么 wqs 二分使用的前提是 $f(x)$ 具有凸性。
換句話說，所有的點 $(i,f(i))$ 共同形成一個凸包。

（以下以上凸包為例，下凸包同理）
考慮對這個凸包做一條斜率為 $k$ 的切線，切于點 $(x,f(x))$。
如何找到這條切線呢？
注意到，切線在 $y$ 軸上的截距必然是最大的。
設截距 $D=f(x)?kx$，我們就使要對于所有 $x$，求出 $D$ 的最大值。
注意到 $?kx$ 這一項，那么我們只需要把每個物品的價值減去 $k$，然后直接求最大值即可。
如果這個切點不在我們需要的 $m$ 處，由于這個切點橫坐標是隨 $k$ 單調的，所以我們可以二分尋找，直到可以切到 $m$ 的 $k$ 為止。
找到正確的 $k$，求出對應的 $D$ 后，$f(x)$ 就等于 $D+kx$，也就不難得到了。

一些細節：

切點很坐標關于 $k$ 的函數并不是連續的，因此可能需要最后一步強制選 $m$ 個來算出答案，對應的，我們也最好把恰好取 $m$ 個的情況歸到大于 $m$ 個的那邊。

如果我們把相等的情況歸于大于，那么在物品權值相等的時候我們就需要把特殊物品優先，這樣如果我們強制拋棄才不會出現選不夠 $m$ 個的情況。

例題

給出一張圖，求出在滿足 $1$ 的度數恰好為 $m$ 的情況下的最小生成樹。

顯然最小生成樹權值關于 $1$ 的度數是一個凸函數。
那么我們就二分一個 $k$，令所有和 $1$ 相連的邊權值減去 $k$，跑一邊最小生成樹，看 $1$ 的度數和 $m$ 大小關系即可。

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=1e6+100; const int M=1e6+100; const int mod=1e9;int n,m,s,k;struct edge{int x,y,w,op,id; }e[N]; bool cmp(edge x,edge y){if(x.w!=y.w) return x.w<y.w;else return x.op>y.op; } int fa[N]; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]); } ll ans; int q[N],num; int check(int val,int op=0){ans=0;//printf("\nval=%d op=%d\n",val,op);for(int i=1;i<=m;i++){e[i].op?e[i].w+=val:0;}for(int i=1;i<=n;i++) fa[i]=i;sort(e+1,e+1+m,cmp);int o=n,d=0;for(int i=1;o>1&&i<=m;i++){int x=find(e[i].x),y=find(e[i].y);//printf("(%d %d) val=%d\n",e[i].x,e[i].y,e[i].w);if(x==y) continue;if(op&&d==k&&e[i].op) continue;//printf(" ok\n");--o;d+=e[i].op;fa[x]=y;ans+=e[i].w;if(op) q[++num]=e[i].id; }ans-=d*val;if(o>1){printf("-1\n");exit(0);}for(int i=1;i<=m;i++){e[i].op?e[i].w-=val:0;}return d; }signed main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifn=read();m=read();s=1;k=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();e[i]=(edge){x,y,w,x==s||y==s,i};}int st=-4e4,ed=4e4;while(st<ed){int mid=(st+ed+1)>>1,num=check(mid);if(num>=k) st=mid;else ed=mid-1;//printf("mid=%d num=%d\n",mid,num);}if(st==-4e4) printf("-1\n");else{int nm=check(st,1);//printf("st=%d num=%d\n",st,num);printf("%d\n",num);for(int i=1;i<=num;i++) printf("%d ",q[i]);}return 0; } /* 5 6 1 3 1 2 2 1 4 5 1 5 5 1 3 2 3 5 4 2 4 4 */

總結

以上是生活随笔為你收集整理的模板：wqs二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。