https://www.matiji.net/exam/brushquestion/14/4347/179CE77A7B772D15A8C00DD8198AAC74
题意:
一群小猫在跑步,给出每个小猫的出发位置和速度,如果路上有小猫遇到了另一个小猫,那么将会和速度较慢的小猫一个速度一组跑步,出发位置一样的小猫直接一组跑步;求最多有多少只小猫一组跑步
const int N = 2e5 + 10;
struct sb
{
int p, v;
}a[N];
bool cmp(sb x, sb y)
{
if(x.p != y.p) return x.p < y.p;
return x.v < y.v;
}
int main()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i].p >> a[i].v;
sort(a + 1, a + 1 + n, cmp);
for(int i = 1; i < n; i ++)
if(a[i].p == a[i + 1].p)
a[i + 1].v = a[i].v;
//原: 6 1; 1 1; 3 2; 1 2; 2 3;
//排序后: 1 1; 1 2; 2 3; 3 2; 6 1;
//此刻的p和v: 1 1; 1 1; 2 3; 3 2; 6 1;
//因为是同位置的速度是从小到大的,现在是统一速度
int ans = -1, cnt = 1, in = n;
/*因为我们已经按照速度从小到大排序了,
当位置不同时, 且位置也是从小到大, 我们现在从后往前遍历
如果说后面的猫(in)的速度小于前面的猫(in-cnt)的速度,那么意味着一定可以被追上成为一组
或者在同一个位置,那么就可以纳为一组
如果说,并不满足以上条件, 就重新化组*/
while(1)
{
//in表示从后往前遍历
if(in - cnt == 0) break;
//cnt是当前组有多少小猫
//两只猫的位置不同但是后猫的速度更快 || 两只猫的速度相同
if((a[in].p != a[in - cnt].p && a[in].v < a[in-cnt].v )|| a[in].p == a[in - cnt].p)
cnt ++;
else
in = in - cnt, cnt = 1;
ans = max(ans, cnt);
}
cout << ans << endl;
}