二分+优先队列例题总结(icpc vp+牛客小白月赛)
题目
思路分析
要求输出最小的非负整数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();
}
代码技巧
-
每次
a[i]都对3进行向上取整，直接(a[i]+2)/3;同样的，对3进行向下取整，直接(a[i]-2)/3。即对k进行向下或向上取整的公式为:a[i]=(a[i]-k+1)/k -
用一个b数组模拟第k轮的情况，每一轮的结果为
b[i]*pow(2,k);
原文地址：https://blog.csdn.net/codekingo/article/details/142442610
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！