腾讯4.5笔试编程题思路+代码

第二题，给你一个只有0和1的字符串，你现在有一个操作，可以把相邻的一对0和1消去，问最后能得到最短长度。 其实这个题就是智商题，仔细想一下，只要字符串里边还有0和1同时存在，那么就一定还能消去，实际上答案就是字符串长度-0和1中数量较少者的数量*2。 上代码 #include<stdio.h> #include<algorithm> using namespace std; int n; char s[200010]; int main() {     scanf("%d",&n);     scanf("%s",s);     int num0=0,num1=0;     for(int i=0;i<n;i++)     {         if(s[i]=='0')             num0++;         else             num1++;     }     int ans=n-min(num0,num1)*2;     printf("%d",ans); }

第一题，你有n种不同面值的硬币，每种硬币有无数个，现在你有可能找零1-m的任意数值，问你最少带着多少枚的硬币能够应对所有找零的情况。如果无解输出-1 题意很好理解，就是你现在选择的这些硬币能够拼成1-m的任意数值，并且要求硬币数量尽可能的少就行了。 其实做法也很简单，就是一个简单的贪心，会想单一的找零问题，我们会选择优先用大面值的硬币找零，以减少找零的硬币数量，当没有办法正好找零时才会换用小面值的硬币。但是我们现在要应对任意可能的找零数值，我们就要转变一下思路。 具体来说，我们先对n种不同的硬币面值进行排序。每一次我们都要尝试用前i-1种硬币来拼成1到第i种硬币面值-1的所有数值，以此来贪心的求解最优解。 接下来我们思考一下贪心的正确性。其实这部分就很好想了，当我们如果以这种方式选择硬币之后，我们现在所得的硬币是不是刚好能够满足任意的找零问题的最优解的情况？ 具体来说看代码就行了 #include<stdio.h> #include<algorithm> using namespace std; int m,n; int num[110]; int main() {     scanf("%d %d",&m,&n);     for(int i=0;i<n;i++)     {         scanf("%d",&num[i]);     }     sort(num,num+n);     if(num[0]!=1)     {         puts("-1");         return 0;     }     else     {         int sum=1;         int ans=1;         for(int i=1;i<n;i++)         {             if(sum>=m)                 break;             int temp=num[i]-sum-1;             ans+=(temp/num[i-1]);             sum+=(temp/num[i-1])*num[i-1];             if(sum<num[i]-1)             {                 ans++;                 sum+=num[i-1];             }         }         if(sum<m)         {             int temp=m-sum;             ans+=temp/num[n-1];             if(temp%num[n-1]!=0)                 ans++;         }         printf("%d\n",ans);     } }

嗯，第三题数据不好，我随便写的也过了

第三题，你要通过怪兽谷，途中你会顺序遇到n只怪兽，每个怪兽有一个武力值，和一个雇佣价格，你要保证你在遇到第i只怪兽时，护卫你的怪兽的战力和大于等于第i只怪兽的战力，否则你就要雇佣它。问你安全通过怪兽谷的最低花费。 其实这个题数据出水了，当时时间不太够，我直接写了个贪心，明显想到就直接过了 代码如下 #include<iostream> #include<algorithm> using namespace std; int n; long long d[55]; int p[55]; int main() {     cin>>n;     for(int i=0;i<n;i++)         cin>>d[i];     for(int i=0;i<n;i++)         cin>>p[i];     long long sum=0;     int ans=0;     for(int i=0;i<n;i++)     {         if(sum<d[i])         {             sum+=d[i];             ans+=p[i];         }     }     cout<<ans<<endl; } 但是这种思路是有问题的，比如说下面这组数据 6 5001 1 1 5000 5000 10000 1 1 1 1 1 2 比如说这组数据，用上述代码计算的答案是3，实际上只用雇佣第一只和第四只就行了，也就是说最低费用是2，而不是3 正确的做法应该是一个背包，用容量代表花费的钱数，里边存的是可以获得的最高战斗值，稍微需要注意一下的就是，一个是战斗力会超过int，一个是中间需要判断非法情况。 具体的来看代码 #include<iostream> #include<algorithm> using namespace std; int n; long long d[55]; int p[55]; long long dp[55][111]; int main() {     cin>>n;     for(int i=1;i<=n;i++)         cin>>d[i];     for(int i=1;i<=n;i++)         cin>>p[i];     long long mx=0;     for(int i=1;i<=n;i++)     {         for(int j=n*2;j>=p[i];j--)         {             dp[i][j]=max(dp[i-1][j],dp[i-1][j-p[i]]+d[i]);         }         mx=max(mx,d[i]);         for(int j=n*2;j>=0;j--)         {             if(dp[i][j]<mx)                 dp[i][j]=0;         }     }     for(int i=1;i<=n*2;i++)     {         if(dp[n][i]>0)         {             cout<<i<<endl;             break;         }     } }