首页 > 其他分享 >滴滴9.13笔试

滴滴9.13笔试

时间:2024-09-14 17:24:47浏览次数:12  
标签:tmp h1 int 滴滴 笔试 9.13 cin h2 op

难度不大,第二题的\(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

相关文章

  • 笔试常用api
    常用apiArrayList:List接口publicbooleanadd(Ee):将指定的元素添加到此集合的尾部。publicbooleanaddAll(collection对象):将collection的对象加入到publicEremove(intindex):移除此集合中指定位置上的元素。返回被删除的元素。publicEget(intindex):返回此集......
  • 美团笔试2024秋1
    1、图染色法在编译原理中,寄存器分配是代码优化阶段的一项重要任务。寄存器分配的目标是为了有效地将程序中的活跃变量映射到有限数量的处理器寄存器上。在这个过程中,图染色法是一种常用的技术,它通过构建一个冲突图(其中节点代表活跃变量,边代表不能同时分配到同一寄存器的变量对......
  • 2024.9.13(周五)
    完成机器学习查询数据集的作业数据集名称样本数属性属性个数标签任务Iris数据集150花萼长度,花萼宽度,花瓣长度,花瓣宽度4鸟类(Setosa,Versicolor,Virginica)分类MNIST数据集70,000像素值(28x28像素)784手写数字(0-9)分类Titanic数据集891乘客ID,船舱......
  • 2024.09.13练习总结
    没有参与比赛练习,所以没有赛时总结。$T1,T2$比较简单,似乎是签到题。$T3$题意不是很懂。首先将题目中的要求转换为人话:当两个区间有交,他们必须长度相同。注意到题目中说有$n$个人要上下电梯,且每站只会有一个人的状态改变。那么不难发现对于一段区间$[l,r]$......
  • 2024.9.13训练记录
    下午ARC104模拟短时赛:T1、T2:T1签到题。T2签到题,\(O(n^2)\)乱做。但是实际上可以空间换时间开桶到\(O(n)\)。也非常简单。T3:考场没有做出。思考的关键在于想到可以对于区间单独判断是否满足条件。知道了如何判断区间是否满足条件后,可以做一次\(O(n)\)的\(dp\)。每次枚......
  • 学习笔记 韩顺平 零基础30天学会Java(2024.9.13)
    P545TreeMap源码解读     TreeSet的k-v其中的v是一个静态的对象,但是TreeMap的v是可以变化的     TreeMap使用默认构造器取出的顺序和添加的顺序是不一样的,但是有构造器实现了Comparator接口的匿名内部类,可以按顺序排序P546Collections工具类1P547Collect......
  • 9.13 模拟赛(炼石计划 11 月 04日 CSP-S 十连测 #7)
    炼石计划11月04日CSP-S十连测#7【补题】-比赛-梦熊联盟(mna.wang)复盘基本上一眼秒了T1,先写这题。在8:30写完了对拍。用了将近一个小时。然后放到桌面2就没管,一直拍到了比赛结束。T2什么牛魔题面???出题人学过语文吗???T3把题读懂了,但是一直不能正确模拟出样例1,......
  • Java笔试面试题AI答之单元测试JUnit(4)
    文章目录19.简述JUnitorg.junit.TestSuite类的作用?1.组织测试类2.简化测试执行3.灵活配置测试环境4.嵌套测试套件注意事项20.在JUnit中@Test注释的作用和用法?作用用法21.简述Junit基础注解(@BeforeClass、@Before、@Test、@After、@AfterClass)?22.编写代......
  • java学习9.13
    将java测试卷重新完成,测试完后基本完成需求,无明显BUG结合课堂上去写这个java测试卷,总的来说,之前没有独立写过类似项目+限时是比较大的问题。如果之前没有经历类似的情况,很多功能都是第一次用,那么就会导致出现bug而不知道如何去改,并且加上时间限制,如果时间全花在改bug上,又无法完......
  • NFLS 2024.9.13 T4
    题意给出一棵以\(1\)为根的树\((n\le10^4)\)和\(k(k\le10^{14})\)。要求给每个点一个\(a_i\)使得\(a_i\mida_{fa_i}\),且\(\proda_i\lek\)。思路这题有一个很妙的思路,但不是前面。设最终的\(\proda_i=S\),可以对\(S\)的每个质因子单独考虑。设\(g(s)\)......