AcWing 1660. 社交距离 II(二分+双指针)
原题链接
简单
作者:
白墙
,
2022-02-15 22:28:57
,
所有人可见
,
阅读 297
// Problem: 社交距离 II
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1662/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 2022-02-15 21:19:40
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define pii pair<int, int>
#define mset(s,t) memset(s,t,sizeof(t))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define fir first
#define pb push_back
#define sec second
#define sortall(x) sort((x).begin(),(x).end())
inline int read () {
int x = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= (ch=='-'),ch= getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return f?-x:x;
}
template<typename T> void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) print(x/10);
putchar(x % 10 + '0');
}
int n;
vector<pii> a;
bool check (int tar) {
bool f =1;
for (int i = 1; i <= n; i ++) {
if (a[i].sec) continue;
if (i == 1) {
if (a[i + 1].sec&& a[i + 1].fir - a[i].fir <= tar) return 0;
}
else if (i == n ) {
if (a[i - 1].sec && a[i].fir - a[i - 1].fir <= tar) return 0;
}
else {
if (a[i - 1].sec)
if (a[i].fir - a[i - 1].fir <= tar) return 0;
if (a[i + 1].sec)
if (a[i + 1].fir - a[i].fir <= tar) return 0;
}
}
return 1;
}
void solve() {
cin >>n;
a.pb({0, 0});
for (int i = 0; i< n ;i ++)
{
int x, y;
cin >> x >> y;
a.pb({x, y});
}
sort(a.begin(), a.end());
int l = 0, r = 1e9;
while (l < r) {
int mid = l + r + 1>> 1;
if (check(mid)) {
l = mid;
}
else r = mid - 1;
}
//二分找到最大的满足要求的R
int ans = 0;
for (int i = 1, j = 2; i <= n; i++)
{
j = i + 1;
if (a[i].sec == 0) {
continue;
}
while (j <= n && a[j].fir - a[j - 1].fir <= l) j ++;
ans++;
i = j - 1;
}
//双指针找到分组个数
cout << ans << endl;
}
int main () {
int t;
t = 1;
while (t --) solve();
return 0;
}
二分找到最大的r。然后用双指针扫描。