太原浪潮VS比亚迪西安规划院

第一题import java.util.*;public class test {    public static void main(String[] args) {        Scanner in=new Scanner(System.in);        int n=in.nextInt();        int k=in.nextInt();        int[] a=new int[100005];        int ai;        int st=100005,ed=0;        for(int i=0;i<n;i++){             ai=in.nextInt();             a[ai]=1;             if(i==0) st=ai;             if(i==n-1) ed=ai;        }        int moreDay=k-n,ans=0,kDay=0;        TreeMap<Integer,Integer> kDayMap=new TreeMap<>();        for(int i=st-1;i<=ed+1;i++){            if(a[i]==0&&a[i+1]==1) {                ans++;                if(i<=st) continue;                kDay++;                if(kDayMap.containsKey(kDay)){                    kDayMap.put(kDay,kDayMap.get(kDay)+1);                }else kDayMap.put(kDay,1);//                System.out.println("day:"+i+"kDay:"+kDay);                kDay=0;            }            else if(a[i]==1&&a[i+1]==0) {                ans++;            }            else if(a[i]==0) kDay++;        }        Set<Integer> kDaySet=kDayMap.keySet();//        System.out.println(kDaySet+"/"+ans+"/"+moreDay);        for(int key:kDaySet){//            System.out.println(key);//            System.out.println(kDayMap.get(key));            int value=kDayMap.get(key);            if(key*value<=moreDay){                moreDay-=key*value;                ans-=value*2;            }else {                ans-=(moreDay/key)*2;                moreDay=0;            }            if(moreDay==0) break;//            System.out.println("key:"+key+" value:"+value+" moreday:"+moreDay+" ans:"+ans);        }        System.out.println(ans);//        System.out.println(moreDay);//        System.out.println(kDayMap);        in.close();    }}第二题来不及做打表#牛客创作赏金赛#

#小米求职进展汇总#1.作为一个登山爱好者，Bo现在正计划向珠峰发起桃战，要问为什么的话，因为山就在那里！珠峰的气候变幻莫测，并不是每天都适合登山，但Bo通过东方神秘力量了解到接下来有个特定日期可能会是适合登山的好日子。因此他在这n天一定要在珠峰大本营等待良机。然而，海拔5200米的珠峰大本营不是久居之地。根据医生的评估，Bob最多能够在此处生活的总天数为k天，否则出现生命危险的概率将大大增加。因此Bob需要注意在不适合登山的日子下撤回低海拔地区。下撤回低海拔地区和前往珠峰大本营的旅费不可小觑，Bob自身也讨厌频繁移动。因此请你告诉他，在不错过个特定日期，同时在珠峰大本营生活不超过总共k天的前提下，最少需要多少次移动？注意，Bob一开始位于低海拔地区，最终也必须回到低海拔地区。一次移动指的是单程而非往返，即从低海拔地区前往珠峰大本营或从珠峰大本营下撤回低海拔地区分别是一次移动。读题读半天，还没写出来2.车辆选配，没写

出差强度极大，开发和产品都要长期出差，一月至少3周在外出差，忙的时候甚至整月出差，最抽象的是，有这么大的出差需求，面试时竟然不提前告知；加班内卷更是常态，出差期间实习生加班到十点是常态，最忙的时候实习生加班到两三点，正式工通宵，加班费一分没有（据说早期是有加班费的，但只有10元/h，可笑不可笑，太侮辱人了），而且浪潮内部每月会统计加班时长进行排名，作为绩效考评指标，所以即使不忙的时候，也会看到员工在工位摸鱼也不下班；正式工出差补助只有可怜的100/天，实习生没有，浪潮实习生工资虽然在招聘平台标注为150/天，但实际只有本科2500/月，研究生3000/月（均包含500的绩效），但是通信有个奇葩惯例，离职当月绩效全扣，意思是即使离职当月满勤，出差加班样样没少，绩效照样一分没有，实习生工资本就少到只能解决温饱，临离职就几百块钱的绩效还全被克扣了，极其恶心

第一题：爬山首先俺们的Bob在一个风和日丽的日子选择去登珠峰，我们需要在n个特殊的日子（人话就是n天时间内）在大本营找到合适的时间去登山。但是需要知道补给只能维持k天，所以Bob最多只能待k天时间，所以他可能会在不适合爬山的日子撤回到低海拔地区。下撤是需要考虑移动次数的。所以我们需要算的就是他在低海拔出发低海拔结束，在不错过n个日子且在大本营生活天数不超过k天的前提下最少的移动次数是多少。思路首先我们将输入进行拆分，举个例子，[2,3,4,7,8]五天时间，我们拆分为[2,3,4]和[7.8]两个区间，每个连续区间内他都只需要进入一次大本营，离开一次，所以我们区间数（最开始统计到的连续区间）p就是至少需要移动的一半。接下来我们来优化移动次数设p为最开始的连续区间数，假设我们停留k天，有n天时间登山，实际上额外停留时间为k - n。所以现在计算非登山日的间隔天数，我们将间隔从小到大排序，尽可能多利用可用额外的停留天数来减少p。具体操作为：从最小的间隔开始，如果还能住，就可以减少一次移动机会（即合并两个区间），直到不能合并就可以得到p的最后结果即移动次数。第二题：买车某人要去买车，需要保证载X人，拉货Y吨，有n种车。对第i种车价值mi元，有ki种方案，默认拉人xi，拉货yi。第i种方案需要mij元，可以选配件让拉人为xij拉货为yij。但是只能选一种。然后要买多种车需要最少的钱。思路相信所有人百分百第一眼看到这题第一反应是，这人有毛病吧！好我们梳理一下首先，问题就是至少载X人，至少载Y吨货，然后花费最少。可以选择的方案有多种，最基本的为mi元，xi人，yi吨。或者别的。解决方案：我们把每种汽车和方案都看成一个“物品”，费用就是汽车的价格，收益就是购买某个汽车后它有一定的承载能力。也就是说我们可以直接转化为一个二维费用的完全背包问题。对于该问题直接采用动态规划。假设dp[x][y]满足至少x人y吨且花费最小接下来定义方程最开始dp[0][0]=0即初始状态。依次遍历所有的方案（cost, cap_x, cap_y）：​完全背包的思想：同一种车买多次，每次购买都会增加承载能力​朴素的完全背包思想：从小到大遍历x, y：dp[min(X, x + cap_x)][min(Y, y + cap_y)] = min(dp[min(X,x+cap_x)][min(Y,y+cap_y)],dp[x][y]+cost)计算过程就是累计遍历所有的方案逐步更新dp，最后得到的就是最小花费。这里需要注意我们最后如果值依旧是无穷大则说明无法满足直接返回 -1。代码详细看我主页www.lx02918.ltd。如果没有说明我还没发（尤其是我这篇刚发出来！）然后我第二题是没有完全做出来的，时间超了，最后几分钟实在优化不出来了。