思路
排序 + 枚举 + 双指针
对两类数据按顺序排序,以其中一类从头开始枚举,实际枚举的意义(以le为例)是假设最终位置在$(le[i-1],le[i]]$区间内。同时移动另一类的指针位置,更新答案。具体地,模拟一下这个过程就懂了。假设排序后
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int le[N], ge[N], idx1, idx2;
int main()
{
int n, x;
char op[2];
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%s%d", op, &x);
if(*op == 'G') ge[idx2++] = x;
else le[idx1++] = x;
}
sort(le, le + idx1);
sort(ge, ge + idx2);
int ans = 1e9;
int i = 0, j = 0;
while(i < idx1) {
while(j < idx2 && ge[j] <= le[i]) j++;
ans = min(ans, idx2 - j + i);
i++;
}
printf("%d", ans);
return 0;
}
想的居然一样