2019 腾讯正式批笔试题题解

以你之姓@ 2021-12-17 08:23 441阅读 0赞

/*
    一.n种硬币，求最少数量的硬币使得凑出1~m的面值【贪心】

input：
    4 20
    1 2 5 10
    output：
    5
    
    二.
    消除相邻为0、1的字符串得到的最短长度

input：4 0101 out：0

三.
    贿赂怪兽需要pi的金币，当之前拐走的所有怪兽武力之和小于当前的怪兽武力di，你需要贿赂它，求最小贿赂值
    3 
    8 5 10
    1 1 2
    out:2
    */
    
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<bits/stdc++.h>
    using namespace std;
    
    
    const double PI=acos(-1.0);
    const double eps=1e-6;
    const int maxn = 1e5 + 100;
    
    
    int i,n,m,ans,s;
    int a[maxn];
    int main()
    {
        scanf("%d%d",&m,&n);
        s=1;
        for(i=1;i<=n;i++) cin>>a[i];
        sort(a+1, a+n+1);
        if(a[1]!=1) cout<<"-1"<<endl;
        while(s<m)
        {
            for(i=1;i<=n;i++)
                if(a[i]>s+1) break;
            s+=a[i-1];
            ans++;
        }
        cout<<ans+1<<endl;
    }
    
    
    /****************/
    
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<bits/stdc++.h>
    using namespace std;
    
    
    const double PI=acos(-1.0);
    const double eps=1e-6;
    const int maxn = 2*1e5 + 100;
    
    
    int n,m,ans;
    int a[maxn];
    char s[maxn];
    int main()
    {
        scanf("%d%s",&n,s);
        int c0=0,c1=0;
        for(int i=0;i<n;i++)
            if(s[i]=='0') c0++;
            else c1++;
        cout<<max(c0-c1,c1-c0)<<endl;
    }
    
    
    /***************/
    
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<bits/stdc++.h>
    using namespace std;
    
    
    const double PI=acos(-1.0);
    const double eps=1e-6;
    const int maxn = 2*1e5 + 100;
    
    
    int n,m;
    int p[maxn];
    long long d[maxn];
    long long tot=0;
    long long sum[maxn];
    int dfs(int id,int sum,int len)
    {
        int res=0;
        if(id==len)
        {
            if(sum<d[id]) return p[id];
            else return 0;
        }
        if(sum>=d[id])
            res+=min(p[id]+dfs(id+1,sum+d[id],len),dfs(id+1,sum,len));
        else
            res+=p[id]+dfs(id+1,sum+d[id],len);
        return res;
    }
    int main()
    {
       scanf("%d",&n);
       int ans=0;
       for(int i=1;i<=n;i++) cin>>d[i];
       for(int i=1;i<=n;i++) cin>>p[i];
       cout<<dfs(1,0,n)<<endl;
    }
    /*
    3
    8 5 10
    1 1 2
    
    
    4
    1 2 4 8
    1 2 1 2
    */

1、【贪心】先判断有无解，如果min(硬币面额)>1则无解，因为搭配不出1；有1则有解，因为所有面额都可由1累积出来。

假设当前硬币可以组合出1~5的任意面额，那添加一枚面额为6的硬币就可以搭配出1~11的任意面额——>假设当前硬币面值和为sum，每一次添加硬币时，从大到小搜，将搜到的第一枚面值<=(sum+1)上限的硬币加入，并将计数器ans+1，更新sum值。（sum表示目前小于等于sum的种类可以被表示，那下一次能增加的面额一定小于等于sum+1，因为如果大于了sum+1，那么从sum+1到此之间的值一定不能被满足）

2、【简单数学】稍微自己举几个例子，只要字符串中存在有’0’和’1’，就会发生合并而将字符串的长度缩小，所以只要计算出字符串中’0’和’1’出现的最小次数，然后直接乘以2，再使用总长度减去即可(可以证明，当这个序列0和1都还存在，是可以继续进行消除的，直到某个数字没有)

3、【选择性dfs】选或不选，满足可以击败当前怪兽的条件下有min（选：贿赂即累加当前的，不选：不贿赂）；不能击败直接贿赂

转载于:https://www.cnblogs.com/Roni-i/p/10660124.html