首页 > 其他分享 >wqs二分

wqs二分

时间：2024-10-24 20:35:47浏览次数：7  
标签：二分 cnt le ll wqs mid check define

感觉一般可能要严谨证明的话还是有点麻烦，不如直接打表，或者先老实WA一发 来的快

  • 一般题目会有选恰好k个/次这样的限制
  • 大致就是通过二分斜率，然后通过dp，或者贪心计算出最大/最小值，然后通过判断这个最大/最小值对应的选的个数来调整
  • 需要注意的是，我们计算的相当于是截距，还要+/-kl才是答案

例题

以https://www.luogu.com.cn/problem/CF802N为例
给定两个长度为 \(n\) 的序列 \(a_1, a_2, \ldots, a_n\) 和 \(b_1, b_2, \ldots b_n\)。要求选出 \(i_1, i_2, \ldots, i_k\) 和 \(j_1, j_2, \ldots, j_k\)，满足

  • \(1\leq i_1< i_2<\ldots< i_k\)，\(1\leq j_1< j_2<\ldots< j_k\)。

  • \(i_p\leq j_p\)（\(1\leq p \leq k\)）。

最小化 \(\sum_{p=1}^k a_{i_p}+b_{j_p}\) 的值。

  • 首先我们来感性理解一下
  • 假如我们不考虑k这个限制，因为都是正的，肯定是一个都不选
  • 但是如果我们给每个\(b_i\)都减上一个数x，就有可能出现选的情况，并且随着数x的增大，选的数肯定是越来越多
  • 因此我们可以二分这个x，计算出选了多少个数，从而对x进行调整

更具体的分析

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=1e6+5;
struct node{
	ll x,op;
};
bool operator < (const node &a,const node &b){
	if (a.x!=b.x) return a.x>b.x;
	return a.op>b.op;
}
priority_queue<node> q;
ll n,k,a[N],b[N],ans;
ll check(ll x){
	while (!q.empty()) q.pop();
	
	ll cnt=0;	
	ans=0;
	fo(i,1,n) {
		q.push((node){a[i],0});
		if (b[i]-x+q.top().x<=0) {
			ans+=b[i]-x+q.top().x;
			if (!q.top().op) cnt++;
			q.pop();
			q.push((node){-(b[i]-x), 1});
		}
	}
	
	return cnt;
}
int main(){
//	freopen("data.in","r",stdin);
	
	scanf("%lld %lld",&n,&k);
	fo(i,1,n) scanf("%lld",&a[i]);
	fo(i,1,n) scanf("%lld",&b[i]);
	
	ll l=0,r=1e12,mid;
	while (l<r) {
		mid=(l+r)>>1;
		if (check(mid)>=k) r=mid;
		else l=mid+1;
	}

	check(l);
	printf("%lld",ans+k*l);
	

	return 0;
}
  • 在反悔贪心的时候，注意到是可以取等，并且权值相同时，优先让a在前面，就是为了尽可能的多选数。
  • 也就是说我们得到的是跟这条直线相切的最右端点
  • 因此只有当\(k \le cnt\)时才可能合法
  • 当mid增大时，cnt会增大，因此我们要二分得到最小的mid使得\(k \le cnt\)

[国家集训队] Tree I

题目描述

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 \(need\) 条白色边的生成树。

题目保证有解。

  • 加入我们给每条白色边-x，那么选择x的边数量肯定不会变得更少。
  • 在下面的代码中，我们排序定义了尽可能多选白色边，因此只有当\(k\le cnt\)才是合法的，而当mid增大，cnt也增大，因此我们要的就是最小的mid，使得\(k \le cnt\)
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=1e6+5;
ll f[N],n,m,k,t1,t2,tot,ans;
struct node{
	ll x,y,z,c;
};
bool operator < (const node&a,const node &b) {
	return a.z<b.z;
}
node e1[N],e2[N],e[N];
void R(ll &x){
	ll t=0; char ch;
	for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
	for (;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
	x=t;
}
int find(int x){
	if (x==f[x]) return x;
	return f[x]=find(f[x]);
}
ll check(ll x){
	fo(i,1,t1) e1[i].z-=x;
	ans=0;
	ll i=1,j=1,cnt=0,f1,f2,tot=0;
	
	while (i<=t1 && j<=t2) {
		if (e1[i].z<=e2[j].z)  {
			e[++tot]=e1[i];
			i++;
		}
		else{ 
			e[++tot]=e2[j];
			j++;
		}
	}
	while (i<=t1) e[++tot]=e1[i],i++;
	while (j<=t2) e[++tot]=e2[j],j++;
	
	fo(i,1,n) f[i]=i;
	fo(i,1,m) {
		f1=find(e[i].x); f2=find(e[i].y);
		if (f1^f2) {
			f[f1]=f2;
			if (!e[i].c) cnt++;
			ans+=e[i].z;
		}
	}
	
	fo(i,1,t1) e1[i].z+=x;
	
	return cnt;
}
int main(){
//	freopen("data.in","r",stdin);
//	
	ll c,x,y,z;
	
	scanf("%lld %lld %lld",&n,&m,&k);
	fo(i,1,m) {
		scanf("%lld %lld %lld %lld",&x,&y,&z,&c);
		x++; y++;
		if (!c) e1[++t1]=(node){x,y,z,0};
		else e2[++t2]=(node){x,y,z,1};
	}
	
	sort(e1+1,e1+t1+1);
	sort(e2+1,e2+t2+1);

	
	ll l=-1,r=200,mid;
	while (l<r) {
		mid=(l+r)>>1;
		if (check(mid)>=k) r=mid;
		else l=mid+1;
	}
	
	check(l);
	printf("%lld\n",ans+k*l);
	

	return 0;
}

[ABC218H] Red and Blue Lamps

题面翻译

题意翻译

现在你有 \(N\) 盏灯排成一列，编号为 \(1\) 到 \(N\)。对于任意一盏灯，你可以将其变成红色或蓝色。你想让其中的 \(R\) 盏灯变成红色，\(N-R\) 盏灯变成蓝色。

当第 \(i\) 和 \(i+1\) 盏灯以不同的颜色发光时，你将获得 \(A_i\) 点报酬。

请你计算当有 \(R\) 盏灯为红色，\(N-R\) 盏灯为蓝色时，你所获得的报酬和的最大值。

  • 又是恰好r个这样的限制，假如我们让每个选红色的，都可以加上一个x，那么当x增大时，在最优选择方案下红色的数量只会增大
  • 代码中我选择的是尽可能多选红色,因此只有当\(k\le cnt\)才是合法的，而当mid增大，cnt也增大，因此我们要的就是最小的mid，使得\(k \le cnt\)
#include<bits/stdc++.h>
#define fo(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
#define mk(x,y) make_pair((x),(y))
#define pi pair<ll,ll>
#define eb emplace_back 
#define fi first 
#define se second
using namespace std;
typedef long long ll;
const ll mo = 1e9 + 7;
const ll inf = 1ll << 60;
const int N = 2e5 + 5;
ll a[N], n, k, ans, f[N][2], g[N][2];
ll check(ll x) {
    ans = 0;

    f[1][0] = x; g[1][0] = 1;
    f[1][1] = 0; g[1][1] = 0;

    fo(i, 2, n) {
        if (f[i - 1][0] <= f[i - 1][1] + a[i]) {
            f[i][0] = f[i - 1][1] + a[i];
            if (f[i - 1][0] == f[i - 1][1] + a[i]) {
                g[i][0] = max(g[i - 1][0], g[i - 1][1]) + 1;
            }
            else g[i][0] = g[i - 1][1] + 1;
        }
        else {
            f[i][0] = f[i - 1][0];
            g[i][0] = g[i - 1][0] + 1;
        }

        if (f[i - 1][0] + a[i] <= f[i - 1][1]) {
            f[i][1] = f[i - 1][1];
            if (f[i - 1][0] + a[i] == f[i - 1][1]) {
                g[i][1] = max(g[i - 1][0], g[i - 1][1]);
            }
            else g[i][1] = g[i - 1][1];
        }
        else {
            f[i][1] = f[i - 1][0] + a[i];
            g[i][1] = g[i - 1][0];
        }
        f[i][0] += x;
    }

    ans = max(f[n][0], f[n][1]);


    if (f[n][0] < f[n][1]) return g[n][1];
    else return g[n][0];
}
int main() {

    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    fo(i, 2, n) cin >> a[i];

    ll l = -1e12, r = 1e12, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid) >= k) r = mid;
        else l = mid + 1;
    }

    check(l);

    cout << ans - k * l;

    return 0;
}

标签：二分,cnt,le,ll,wqs,mid,check,define
From： https://www.cnblogs.com/ganking/p/18500412

相关文章

  • P2839 [国家集训队] middle（二分+可持久化线段树）
    P2839[国家集训队]middle二分+可持久化线段树中位数经典做法，二分答案，将小于的部分看做\(-1\)，大于等于的部分看做\(+1\)，那么答案可以更大的条件就是区间和大于等于\(0\)（等于\(0\)可不可以取到看是下取整还是上取整，本题是上取整）。那么问题就是怎么判断有没有这样一个区间......
  • 二分图
    二分图速通定义若一个无向图\(G=(V,E)\)的点集\(V\)可以分解成两个互不相交的子集\(A,B\)，且对于所有边\((i,j)\)的端点\(i,j\)都分别属于子集\(A,B\)中的元素，则称\(G\)是一个二分图。判定一张无向图是二分图，当且仅当图中不存在奇环。故我们有染色算法判定二分图......
  • 二分图
    二分图概念假设\(G=(V,E)\)是一个无向图，若点集\(V\)可以分解成互不相交的子集\((A,B)\)，并且图中所有边\((i,j)\)的端点\(i\)、\(j\)分别属于子集\(A\)、\(B\)，则称\(G\)是一个二分图定理：一张无向图时二分图，当且仅当图中不存在奇环。染色法判定一个图是否是二分图......
  • 二分图学习笔记
    1.概念假设图\(G=(V,E)\)是无向图，若顶点集\(V\)可以分成两个互不相交的子集\((A,B)\)，且任意边\((i,j)\)两端点分别属于两子集，则图\(G\)是二分图判断方法：染色法匹配：无公共点的边集匹配数：边集中边的个数最大匹配：匹配数最大的匹配增广路：设M是一个匹配，如果存在一条连接两个未匹......
  • 二分算法
    今天学了二分算法：在一个有序的列表里找一个数，用for循环，每次比较中间的数和要找的数，要找的数大则将头移到中间的数的下一个数，否则将尾移到中间的数。（头算尾不算）这是代码：#include<bits/stdc++.h>usingnamespacestd;inta[100001];intbs(inta[],intl,intr,intx){ i......
  • Dilworth 定理与二分图部分理论
    给定一个DAG，定义链：一条链内任意两点之间都存在一条路径反链：任意两点都不存在路径Dilworth定理：最长反链\(=\)最小链覆盖。最小链覆盖内一个点只能归属于一条链，但链不一定是连续的。事实上这个还能转化为“选出若干条（一般定义下的）链，但一个点可以在多条链内”，本质相同。......
  • P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶（线段树上二分）
    link赛时是想到普通的线段树+二分\(O(q\log^2n)\)，预期是70pts，实际50pts后面发现又是在longlong类型的计算中，1ll写成了1，然后爆负数，复杂度就错了，T了四个点开题，读起来是一个很套路的题目要对区间在线修改，区间加、（区间乘？），发现数据很大，那就是线段树、树状数组维护了思......
  • 二分查找
    1.好处二分查找（折半查找）效率高，时间复杂度低，但是仅能用于有序数组2.代码及其逻辑二分查找的逻辑就是通过我们想要找到的值与中间量（mid）作比较，来不断缩小范围，如果说我们想要查找的值比中间量要大，那么我们就会取前半个区间，在进行一次与中间量的比较，不断的循环，就能找到我们想要查......
  • 二分求操作后的最大最小中位数
    这类题是让你求对序列进行一系列操作之后的最小/最大中位数求最小中位数二分最小中位数，显然二分要符合mid越大越对，边界才能向下收缩。对于这个条件，我们选择计算小于等于当前mid的数才是对的，因为这样显然mid越大cnt越大，而符合这个条件，我们就不断收缩上界，直到达到第......
  • Matlab使用LSTM或BiLSTM对一维信号(语音信号、心电信号等)进行二分类源程序。也可以改
     Matlab使用LSTM或BiLSTM对一维信号(语音信号、心电信号等)进行二分类源程序。也可以改成多分类。包含数据和代码，数据可以直接替换为自己的数据。如果用BiLSTM，程序中只需要把lstmlayer改为bilstmlayer即为BiLSTM网络，其他地方不需要任何改动。工作如下：1、加载数据集，一共为......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99