美团笔试算法岗

第一题不是力扣原题

第二题正确的思路应该是啥？求指点

第二题 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<ctime> #include<random> #define ll long long #define Fori(x) for(int i=0;i<x;i++) #define Forj(x) for(int j=0;j<x;j++) using namespace std; int n; int a[111]; int b[111]; int dp[111][10011]; int main() {  Fori(111)   Forj(10011)    dp[i][j] = -100000000;  dp[0][0] = 0;  scanf("%d",&n);  Fori(n)   scanf("%d",&a[i]);  Fori(n)   scanf("%d",&b[i]);  for(int i=0;i<=n;i++)  {   for(int j=n;j>=1;j--)   {    for(int k=10000;k>=b[i];k--)    {     dp[j][k] = max(dp[j][k],dp[j-1][k-b[i]]+a[i]);    }   }  }  int sum = 0;  int ans = 0;  for(int i=0;i<n;i++) sum+=a[i];  sort(b,b+n);  int tmp = 0;  for(int i=n-1;i>=0;i--)  {   tmp+=b[i];   if(sum<=tmp)   {    ans = n-i;    break;   }  }  cout<<ans<<" ";  int ans2 = 10000000;  for(int i=sum;i<=10000;i++)   ans2 = min(ans2,sum - dp[ans][i]);  cout<<ans2<<endl;  return 0; }

怎么看错误事例啊？ 开放题的题目是确定能搜出来。。所以算的应该不是期望是最坏情况。。。

我也想知道咋看到的错误实例。。。还是说你猜了一个错误实例出来？

问答题和经典的两个鸡蛋测在第几层碎一样，有很多种方法，也可以dp

问答题是两个鸡蛋测楼层的问题，答案是 17好像n(n+1)\2=150