难度不大,第二题的\(O(n)\)带有一点思维
第一题
滑动窗口板子题: 求和不超过m的最大区间长度
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long m;
cin >> n >> m;
vector<int> nums;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
nums.push_back(tmp);
}
int left = 0;//[left, right]
long long sum = 0;
int res = 0;
for (int i = 0 ; i < n; i++) {
sum += nums[i];
while (left <= i && sum > m) {
sum -= nums[left++];
}
if (left <= i) {
res = max(res, i - left + 1);
}
}
cout << res;
}
// 64 位输出请用 printf("%lld")
第二题
给出数字n和对应的n个数对[op,x],其中op有将x名次保持原状的0,将x名词调后的1,将名词调前的-1,保证[1,n]个数字只会被调整一次,输出是否存在合理的序列满足所有调整。
排序后查看1和-1操作次数是否对得上\(O(nlogn)\)
此处贴上\(O(n)\)做法
核心思想:只有在试图占据前k个位置的数超过k的时候才不符合条件
调整策略(贪心):将名次调整到前面,也就是至少上升一位,反之亦然;不调整名词则是占据当前位置。分别使用两个差分数组来表示,k位置前(或后)面会有多少数字
判断:将差分数组加和,对两个数组的前缀(或后缀)和进行判断,均符合要求即成立
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int h1[N];
int h2[N];
int main() {
int T;
cin >> T;
while (T--) {
memset(h1, 0, sizeof(h1));
memset(h2, 0, sizeof(h2));
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int op,x;
cin >> op >> x;
if (op == -1) {
h1[x - 1] += 1;
}
if (op == 0) {
h1[x] += 1;
h2[x] += 1;
}
if (op == 1) {
h2[x + 1] += 1;
}
}
bool flag = true;
int tmp = 0;
for (int i = 0; i <= n; i++) {
tmp += h1[i];
if (tmp > i) {
flag = false;
break;
}
}
tmp = 0;
for (int i = n + 1; i>= 1; i--) {
tmp += h2[i];
if (tmp > n - i + 1) {
flag = false;
break;
}
}
if (flag) cout <<"YES"<<endl;
else cout <<"NO" <<endl;
}
return 0;
}
标签:tmp,h1,int,滴滴,笔试,9.13,cin,h2,op
From: https://www.cnblogs.com/tanch25/p/18414399