60pts 双指针RE求条
查看原帖
60pts 双指针RE求条
1365127
dendky楼主2025/8/1 17:31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, zz=1;
ll b[50000005], ans;
bool check;
struct node {
	ll x, id, flag;
}a[50000005];
bool cmp(node x, node y) {
	return x.x<y.x;
}
bool cmp2(node x, node y) {
	return x.id<y.id;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
//	cout<<1;
	cin>>n>>m;
	for (int i=1; i<=n; i++) {
		cin>>a[i].x;
		a[i].id=i;
	}
	for (int i=1; i<=m; i++) cin>>b[i];
	sort(a+1, a+1+n, cmp);
	sort(b+1, b+1+m);
	for (int i=1; i<=n; i++) {
		if (a[i].x==b[zz]) 
			a[i].flag=1;
		if (a[i].x>b[zz]) zz++, i--;
	}
	sort(a+1, a+1+n, cmp2);
//	for (int i=1; i<=n; i++) cout<<a[i].x<<" ";
//	cout<<endl;
//	for (int i=1; i<=n; i++) cout<<a[i].flag<<" ";
//	cout<<"\n";
	a[n+1].flag=1;
	a[0].flag=1;
	for (int i=1; i<=n+1; i++) {
		if (check==0 && a[i-1].flag && a[i].flag==0) 
			check=1;
		if (check && a[i+1].flag && i!=(n+1) && a[i].flag==0) {
			check=0;
			ans++;
		}
//		if (a[i+1].flag==0 && a[i].flag) check=0;
//		cout<<check<<" ";
	}
//	if (a[1].flag==0 && a[2].flag) ans++;
	cout<<ans;
	return 0;
}/*
6 2
3 3 3 3 3 3
3 4

6 2
5 5 5 5 6 5
3 4
*/
2025/8/1 17:31
加载中...