字节跳动 c++ 笔试题 2020-04-12

A题

给俩数组a和b，然后能给a的连续一段加上一个数，问能否让a变成b

模拟题意，别漏情况

#include<bits/stdc++.h>
#define LL long long
#define maxn 100010
using namespace std;

int a[maxn], b[maxn];

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		int n;
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			scanf("%d", &a[i]);	
		}
		for(int i = 0; i < n; ++i){
			scanf("%d", &b[i]);
		}
		int l = 0, r = n, t = 2;
		bool ok = true;
		for(int i = 1; i < n; ++i){
			if((a[i] - b[i]) - (a[i - 1] - b[i - 1]) != 0){
				if(t == 2){
					l = i;
					t--;
				}
				else if(t == 1){
					r = i;
					t--;
				}
				else{
					ok = false;
				}
			}
		}
		//cout << l << " " << r << endl;
		int ch = b[l] - a[l];
		for(int i = l; i < r; ++i){
			a[i] = a[i] + ch;
		}
		for(int i = 0; i < n; ++i){
			if(a[i] != b[i]){
				ok = false;
			}
		}
		printf(ok ? "YES\n" : "NO\n");
	}
	return 0;
}

B题

有一排木条，各自有长度，每根木条可以拆成长度和为原木条长度的两段，问你让它们单调不减的最小拆分次数

从前往后记录最小值，挺良心的，不用二分也能过

#include<bits/stdc++.h>
#define LL long long
#define maxn 3010
#define INF 0x3f3f3f3f
using namespace std;

int a[maxn];

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &a[i]);
	}
	int ans = 0;
	int mi = INF;
	for(int i = n - 1; i >= 0; --i){
		mi = min(a[i], mi);
		if(a[i] > mi){
			double d = 2;
			while(ceil(a[i] / d) > mi){
				d++;
			}
			ans = ans + d - 1;
			mi = min(mi, int(floor(a[i] / d)));
		}
	}
	printf("%d\n", ans);
	return 0;
}

C题

有一堆优惠券a，商品b，如果bi>=aj的话bi可以被优惠aj元，aj永远不会消失，问最少花费

二分裸题，找ai中第一个小于等于bi的值

#include<bits/stdc++.h>
#define LL long long
#define maxn 3010
#define INF 0x3f3f3f3f
using namespace std;

int a[maxn], b[maxn];

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i){
		scanf("%d", &a[i]);
	}
	for(int i = 0; i < m; ++i){
		scanf("%d", &b[i]);
	}
	sort(a, a + n);
	LL sum = 0;
	for(int i = 0; i < m; ++i){
		int p = upper_bound(a, a + n, b[i]) - a;
		sum = sum + b[i] - a[p - 1];
	}
	printf("%lld\n", sum);
	return 0;
}

D题

有一排楼房，向左看最远会被比自己高的楼挡住，向右看一样，问每个楼最远能看到多少楼

单调栈裸题，两遍记录答案就行了

#include<bits/stdc++.h>
#define LL long long
#define maxn 100010
#define INF 0x3f3f3f3f
using namespace std;

int a[maxn], ans[maxn];

stack<int> st;

/* 
1
4
1 4 3 3
*/

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		int n;
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			scanf("%d", &a[i]);
		}
		memset(ans, 0, sizeof ans);
		while(!st.empty()){
			st.pop();
		}
		for(int i = 0; i < n; ++i){
			if(st.empty() || a[i] < a[st.top()]){
				st.push(i);
			}
			else{
				while(!st.empty() && a[i] >= a[st.top()]){
					st.pop();
				}
				if(st.empty()){
					ans[i] = ans[i] + i;
				}
				else{
					ans[i] = ans[i] + i - st.top() - 1;
				}
				st.push(i);
			}
		}
		while(!st.empty()){
			st.pop();
		}
		for(int i = n - 1; i >= 0; --i){
			if(st.empty() || a[i] < a[st.top()]){
				st.push(i);
			}
			else{
				while(!st.empty() && a[i] >= a[st.top()]){
					st.pop();
				}
				if(st.empty()){
					ans[i] = ans[i] + n - i - 1;
				}
				else{
					ans[i] = ans[i] + st.top() - i - 1;
				}
				st.push(i);
			}
		}
		for(int i = 0; i < n; ++i){
			printf("%d ", ans[i]);
		}
		printf("\n");
	}
	return 0;
}

用了大概一个小时，这场的题还是蛮简单的，比阿里笔试题简单一个档次

#字节跳动春招##字节跳动##笔试题目#