您当前的位置: 首页 >  c++

MangataTS

暂无认证

  • 0浏览

    0关注

    423博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

MangataTS 发布时间:2022-06-16 01:50:45 ,浏览量:0

文章目录
    • 前言
    • 一、[编程题]完美序列
      • 1.1 题目连接
      • 1.2 题面
      • 1.3 思路
      • 1.4 代码
    • 二、[编程题]商场收益统计
      • 2.1 题目链接
      • 2.2 题面
      • 2.3 思路
      • 2.4 代码
    • 三、[编程题]大橘为重
      • 3.1 题目链接
      • 3.2 题面
      • 3.3 思路
      • 3.4 代码
    • 四、[编程题]叠大饼
      • 4.1 题目链接
      • 4.2 题面
      • 4.3 思路
      • 4.4 代码

前言

面试的链接: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             
关注
打赏
1665836431
查看更多评论
0.0404s