二分+优先队列例题总结(icpc vp+牛客小白月赛)

题目

20240514101201367.png&pos_id=img-YlbxsILq-1727006761086)

思路分析

要求输出最小的非负整数k，同时我们还要判断是否存在x让整个序列满足上述条件。

当k等于某个值时，我们可以得到x的一个取值区间，若所有元素得到的x的区间都有交集(重合)的话,那么说明存在x满足条件。
因为b[i]的取值为1e9，因为此题不用取模，所以k*b[i]的取值不会超过1e18，所以k的取值范围为0~1e9。我们可以二分枚举k的取值，若不存在x满足条件则往右区间枚举，反之则往左区间枚举。
时间复杂度nlogn。

AC代码

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
const int MAXN=3e5+10;
int n;
int a[MAXN],b[MAXN];bool check(int k) {int xl = a[1] - k*b[1];int xr = a[1] + k*b[1];for (int i = 2; i <= n; ++i) {int ll = a[i] - k*b[i];int rr = a[i] + k*b[i];if (ll > xl) xl=ll;if (rr < xr) xr=rr;}if (xr < xl) return false;return true;
}void solve() {cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];int l=0,r=1e9+1;while(l<r) {int mid=(l+r)/2;if (check(mid)) r=mid;else l=mid+1;}cout << l << endl;
}signed main() {ios ::sync_with_stdio(false);cin.tie(nullptr);int t=1;cin >> t;while (t--) solve();
}

代码技巧

判断区间是否存在交集

bool check(int k) {int xl = a[1] - k*b[1];int xr = a[1] + k*b[1];for (int i = 2; i <= n; ++i) {int ll = a[i] - k*b[i];int rr = a[i] + k*b[i];if (ll > xl) xl=ll;if (rr < xr) xr=rr;}if (xr < xl) return false;return true;
}

题目

在这里插入图片描述

思路分析

贪心思路。要尽可能占最多的线段，那么我们每次应该选择最边缘的坐标保证不会影响到其他线段。

可以对线段的左端点进行排序，如果左端点相等，优先占领右端点小的线段，所以再给右端点进行排序。

由于当两个线段左端点相等时，我们需要将线段的左端点进行更新(右移一位)，重新进行排序。所以可以通过优先队列来维护线段的优先性，来模拟这个过程。

**需要注意的是：**在对线段左端点进行更新的同时，要注意线段的长度，如果线段的长度为0，则无法将左端点右移，则此端点无法被占领。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
int n;
struct node
{int l,r;bool operator < (const node &a) const {if (l==a.l) return r>a.r;return l>a.l;}
}a[MAXN];void solve()
{cin>>n;priority_queue<node>q;for(int i = 1; i <= n ; i ++){cin>>a[i].l>>a[i].r;q.push(a[i]);}int ans=0,tmp=0;node nd;while(!q.empty()) {nd=q.top();q.pop();if (nd.l>tmp) {ans++;tmp=nd.l;}else if (nd.l+1<=nd.r) {nd.l=tmp+1;q.push(nd);}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int t=1;cin>>t;while(t--) solve();return 0;
}

题目

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

思路分析

由于ai的范围小于1e9，也就是最大2^31-1，循环的次数不超过32次，常数级别时间复杂度，可以直接模拟。
如何模拟？

因为每次收割麦子都会得到原来麦子的2倍，且只有最后当麦子等级为x的时候才算是有效的。

所以可以用b数组来模拟，bi代表有多少麦子能在第i轮达到x。最后求出b数组中每一轮小麦的数量×2^i的最大值即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000010;
int n,a[N],x,b[50];
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>x;for(int i=1;i<=n;i++) {int k=a[i];int c=0;while(k>x) {k=(k+2)/3;c++;}if (k==x) b[c]++;}ll maxn=-1;int k;for(int i=0;i<=40;i++) {if (maxn<(ll)b[i]*pow(2,i)) {maxn=b[i]*pow(2,i);}}cout<<maxn;
}int main() {ios::sync_with_stdio(false);cin.tie(0);solve();
}