滴滴两道笔试题

求第一题垃圾车 第二题代码： #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e5+10; int n,m; int a[maxn]; int dp[maxn],sum[maxn]; int main() {     scanf("%d%d",&n,&m);     for(int i=0;i<n;i++){         scanf("%d",&a[i]);         if(i==0)sum[0]=a[0];         else sum[i]=sum[i-1]+a[i];     }     dp[0]=a[0];     for(int i=1;i<m;i++){ //长度<=m时         if(dp[i-1]<0){             dp[i]=dp[i-1]+a[i];         }else {             dp[i]=a[i];         }     }     int Min=sum[m-1];     //printf("%d\n",Min);     for(int i=m;i<n;i++){ //长度>m时         if(dp[i-m]<0){             dp[i]=dp[i-m]+sum[i]-sum[i-m];         }else{             dp[i]=sum[i]-sum[i-m];         }         //printf("%d--%d\n",i,dp[i]);         if(dp[i]<Min)Min=dp[i];     }     printf("%d\n",Min);     return 0; }

第一题不会 第二题 public class Two {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         int[] nums = new int[n+1];         for (int i = 1; i <= n; i++) {             nums[i] = sc.nextInt();         }         int ans = 0;         int[] sum = new int[n+1];         for (int i = 1; i <=n ; i++) {             sum[i] = sum[i-1]+nums[i];         }         int[] dp = new int[n+1];         for (int i = m; i <=n ; i++) {             dp[i] = Math.min(dp[i-1],sum[i-1]-sum[i-m])+nums[i];             ans = Math.min(ans,dp[i]);         }         System.out.println(ans);     } }

第二题跟你们的不一样吗？为啥我的第二题是工作调度😂

第一题，瞎写9%，  n是奇数输出n-1偶数输出n是55%，  加上n>10 n-2是64%， 加上n>20 n-3是66% 🤣

我记得是PDD或者是网易的题，我也后悔了。。😂😂😂

我也用的dp，但是AC不了

他这个是不是可以尾巴连着头的区间

求第二题代码

第二题分享一下可以么大佬

第二题分享一下吧!!

垃圾分类想当然的用了一个map统计不能与自己放在一块的个数，不知道哪里不对，就是过不了😂😂

求第二题分享代码

第一题可以用地图着色问题解，不知道复杂度会不会超

第二题dp超空间了，，改了一下用两个值保存pre和now，结果时间后来也超了，，哭泣

大哥们，现在滴滴招聘的网页没法登陆了么

决定写一波思路的时候，似乎发现自己AC的代码有点问题，应该有些corner case过不了的

太难了 完全写不出来

第一题 55%    第二题 AC。。