【2021】贝壳找房春招C++工程师笔试卷2

前言

面试的链接：https://www.nowcoder.com/test/35148556/summary

牛客的校招面试真题，稍微做了一下，写了快一个小时，不知道为啥只有 90 分，勉强写个题解吧

一、[编程题]完美序列 1.1 题目连接

https://www.nowcoder.com/questionTerminal/4017903f92b6455790b4c670c7176156

1.2 题面

1.3 思路

看一下数据范围 n n n 的范围是 1 e 4 1e4 1e4 ，只要 O ( N 2 ) O(N^2) O(N2) 以内的复杂度都能接受，于是我们可以先将数据处理为 − 1 、 1 -1、1 −1、1 的序列（分别对应小于等于 k k k 的数和大于 k k k 的数），然后对这个序列做一个前缀和，很显然，当一个序列的区间和大于 0 0 0 的时候就是一个完美的序列，那么我们只需要枚举一下区间的左端点，以及区间的长度即可，这样的话整体复杂度 O ( N 2 ) O(N^2) O(N2) 满足题目要求

ps:这里我开始以为能用双指针，琢磨了半小时发现写不出来（

1.4 代码

#include
using namespace std;
#define endl "\n"
const int N = 1e5+10;

int n,k;
int a[N],b[N];

int main()
{
	cin>>n>>k;
	int l = 0,r = 0;
	for(int i = 1;i >a[i];
		a[i] = a[i] > k ? 1 : -1;
		b[i] =b[i-1] +  a[i];
	}
	int ans = 0;
	for(int l = 1;l s>>w>>c;
		st[s]={w,c};
	}
	int err = 0;
	long long sum = 0;
	for(int i = 1;i >s>>c;
		if(st[s].second