#C241126A. 铺设积木

标签（Label）

贪心
差分

网址（Website）

题目详情 - 铺设积木 - Super

题解 - 铺设积木 - Super

题目（Problem）

输入数据 1

5 1
4 3 2 5 3
2 3 4 1 2

输出数据 1

【样例1解释】

在填平阶段，依次选择 $1,5$，$1,5$，$4,4$，$4,4$，$1,1$，最终结果为 $1,1,0,1,1$；

在建造阶段，依次选择 $[3,5]$，$[1,3]$，$[5,5]$，$[1,3]$，$[2,3]$。

【样例2】

见选手目录下的 $roadblock/roadblock2.in$ 与 $roadblock/roadblock2.ans$。

该样例数据满足测试点 $7\sim12$ 的性质。

【样例3】

见选手目录下的 $roadblock/roadblock3.in$ 与 $roadblock/roadblock3.ans$。

该样例数据满足测试点 $13\sim16$ 的性质。

【样例4】

见选手目录下的 $roadblock/roadblock4.in$ 与 $roadblock/roadblock4.ans$。

该样例数据满足测试点 $17\sim20$ 的性质。

题解（Solution）

出题者题解

代码（Code）

100分

#include<bits/stdc++.h>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n';
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x; 
}template<typename G>
void write(G x){
	if(x<0) putchar('-'), write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 201234;
bool ST;

/*
很像之前的一道题，盖楼的时候可以O(n)做
考虑填地
如果往下挖一段，在没有k的限制的情况下对答案没有影响 
考虑先放k的限制，后面就按原来的做法做
直接做差，转换为单点+1，另一个点 -1
使差分数组|c[i]|<=k
直接记录大于k的要操作多少次，小于的要操作多少次，取max即可 
*/

int d[N],h[N],c[N];
int n,k,ans1,ans2;

void Solve(){
	n=rd(),k=rd();For(i,1,n) d[i]=rd();For(i,1,n) h[i]=rd(); 
	For(i,1,n+1) c[i]=d[i]-d[i-1];
	int cnt1=0, cnt2=0;
	For(i,1,n+1){
		if(abs(c[i]) > k){
			if(c[i] > 0) cnt1 += c[i]-k;
			if(c[i] < 0) cnt2 += -k-c[i];
		}
	}ans1 = max(cnt1, cnt2);
	
	int lst = 0;
	For(i,1,n){
		if(lst < h[i]){
			ans2 += h[i]-lst;
		}lst = h[i];
	}write(ans1+ans2), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("roadblock.in","r",stdin);
	freopen("roadblock.out","w",stdout);
	int Tt=1;double Tim = clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}