牛客小白月赛99 E题

多米诺骨牌

题目背景

牛客小白月赛99

题目描述

样例 #1

样例输入 #1

3
6 1
1 1 1 3 2 1
4 3 2 7 9 11
6 2
1 1 1 3 2 1
4 3 2 7 9 11
5 4
1 4 1 1 2
1 2 3 6 8

样例输出 #1

3
6
5

做题思路

按照玩多米诺骨牌的方式。

先将多米诺骨牌按照骨牌位置从小到大排序，相当于摆放好多米诺骨牌。

接着从第一个多米诺骨牌遍历到最后一个多米诺骨牌。

在此期间如果第$i$个多米诺骨牌的位置在$i-1$个多米诺骨牌的倒下范围内，那么“这一堆”多米诺骨牌倒下的个数+1 ； 否则从新开“一堆”多米诺骨牌，并且设置多米诺骨牌倒下个数为1。

最后按照从大到小顺序对“每一堆”多米诺骨牌倒下个数进行排序。

最后取$min(m,堆数)$次多米诺骨牌倒下个数的和作为答案即可。

核心代码：

for(int i=1;i<=n;i++){if(i == 1 || dmn[i].x > last){ // 是第一个多米诺骨牌||不会被前面连带推倒sum[++cnt] = 1;//“这一堆”多米诺骨牌倒下个数设为1last = max(last , dmn[i].x + dmn[i].h);//维护多米诺骨牌倒下范围最大值}else{sum[cnt] ++;//“这一堆”多米诺骨牌倒下个数加一last = max(last , dmn[i].x + dmn[i].h);}}

代码

#include <iostream>
#include <algorithm>
#define int long long
using namespace  std;
const int N = 2e7+10;
int n , m ,k , w , q;
int cnt ,  sum[N];
struct Dmn{int h , x;
}dmn[N];
void init(){}
inline int read()
{char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
void solve(){n=read();m=read();for(int i=1;i<=n;i++){dmn[i].h = read();}for(int i=1;i<=n;i++){dmn[i].x = read();}sort(dmn+1,dmn+1+n,[&](Dmn a , Dmn b){return a.x < b.x;});cnt = 0;int last = 0;for(int i=1;i<=n;i++){if(i == 1 || dmn[i].x > last){ // 是第一个多米诺骨牌||不会被前面连带推倒sum[++cnt] = 1;//“这一堆”多米诺骨牌倒下个数设为1last = max(last , dmn[i].x + dmn[i].h);//维护多米诺骨牌倒下范围最大值}else{sum[cnt] ++;//“这一堆”多米诺骨牌倒下个数加一last = max(last , dmn[i].x + dmn[i].h);}}sort(sum+1,sum+cnt+1,greater<int>());int ans = 0;for(int i=1;i<=min(cnt,m);i++)ans+=sum[i];cout << ans << '\n';
}
signed main(){init();int _=1;_=read();while(_--)solve();return 0;
}