4月5日腾讯后台开发笔试
- 排序+贪心
先判断有无解,如果min(硬币面额)>1则无解,因为搭配不出1;有1则有解,因为所有面额都可由1累积出来。假设当前硬币可以组合出1-5的任意面额,那添加一枚面额为6的硬币就可以搭配出1~11的任意面额——>假设当前硬币面值和为sum,每一次添加硬币时,从大到小搜,将搜到的第一枚面值<=(sum+1)上限的硬币加入,并将计数器ans+1,更新sum值。(sum表示目前小于等于sum的种类可以被表示,那下一次能增加的面额一定小于等于sum+1,因为如果大于了sum+1,那么从sum+1到此之间的值一定不能被满足)
#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
int m,n,j;
scanf("%d %d",&m,&n);
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int s=1;
int num=0;
if (a[0]!=1)
{
cout<<-1<<endl;
}
else
{
while(s<m)
{
for(j=0;j<n-1;j++)
if (a[j+1]-1>s) break;
s+=a[j];
num++;
}
cout<<num+1<<endl;
}
return 0;
}
测试样例
20 4
1 3 5 12 输出5
去除相邻的01问题,转化为求字符串内1的个数0的个数之差。
#include <iostream>
using namespace std;
int main() {
int i,n,num_0,num_1;
num_0=num_1=0;
cin>>n;
string a;
cin>>a;
for (i=0;i<n;i++)
{
if(a[i]=='0')
{
num_0++;
}
else
{
num_1++;
}
}
cout<<abs(num_0-num_1)<<endl;
return 0;
}
测试数据有问题,所以即使编的很简单也过了。不能击败直接贿赂
#include <iostream>
using namespace std;
int main() {
int i,N,sum_d,sum_p;
cin>>N;
int d[N];
int p[N];
for(i=0;i<N;i++)
{
cin>>d[i];
}
for (i=0;i<N;i++)
{
cin>>p[i];
}
sum_d=0;sum_p=0;
for (i=0;i<N;i++)
{
if(sum_d<d[i])
{
sum_d+=d[i];
sum_p+=p[i];
}
}
cout<<sum_p<<endl;
return 0;
}