首页 > 百度笔试3.30 剧组+奶牛
头像
HatsuneHan
编辑于 2021-03-31 10:24
+ 关注

百度笔试3.30 剧组+奶牛

两题整体来说难度适中,第三题数学题实在做不动……
第一题:求剧组中每个人满足要求的角色数目:
#include<bits/stdc++.h>
using namespace std;

int a[1005];
int sum[1005];
int num[105];
int b[1005];

int main()
{
    int T;
    cin >> T;
    while(T--){
        int n,m;
        cin >> n >> m;
        memset(num,0,sizeof(num));
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        int s = 0;
        for(int i = 0; i < m; i++){
            cin >> b[i];
            num[b[i]]++;
        }
        for(int i = 1; i <= 100; i++){
            s += num[i];
            sum[i] = m - s + num[i];
        }
        for(int i = 0; i < n; i++){
            cout << sum[a[i]] << " ";
        }
        cout << endl;
    }
    return 0;
}
扫一遍角色戏份值,记录每个戏份值的数量,然后利用前缀和思想计算每个指标对应的满足要求的角色数目,最后根据每个人心中的指标输出即可。

第二题:输出优质奶牛的编号
这题刚开始没看到区间可能重叠,导致写崩了,后面看到后打了个补丁,所以比较丑
#include<bits/stdc++.h>
using namespace std;

int cnt[1005];
int sum[1005];
int tmp[1005];
int tmp_sum[1005];

int main()
{
    int T;
    cin >> T;
    while(T--){
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        memset(tmp_sum,0,sizeof(tmp_sum));
        int n, m;
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            int k;
            cin >> k;
            while(k--){
                int l, r;
                cin >> l >> r;
                tmp[l]++;
                tmp[r+1]--;
            }

            int sm = 0;
            int flag = 0;
            for(int i = 1; i <= n; i++){
                sm += tmp[i];
                tmp[i] = 0;
                tmp_sum[i] = sm;
                if(flag == 0 && tmp_sum[i] >= 1){
                    cnt[i]++;
                    flag = 1;
                }else if(flag == 1 && tmp_sum[i] < 1){
                    cnt[i]--;
                    flag = 0;
                }
            }

            
        }

        int s = 0;

        for(int i = 1; i <= n; i++){
            s += cnt[i];
            sum[i] = s;
        }

        // for(int i = 1; i <= n; i++){
        //     cout << sum[i] << " ";
        // }

        int ans = 0;

        for(int i = 1; i <= n; i++){
            if(sum[i] == m)
                ans++;
        }
        cout << ans << endl;
        for(int i = 1; i <= n; i++){
            if(sum[i] == m)
                // ;
                cout << i << " ";
        }
        if(ans != 0)
            cout << endl;
    }
    return 0;
}
基本思想:先假设每一个特性所给的区间均不重叠,则初始化一个全为0的数组cnt,当遇到[l,r]区间时,cnt[l]++,cnt[r+1]--,再求一次cnt的前缀和存到sum数组中,则sum[i]=1表示这一奶牛具有该特性,=0则不具有该特性。
对于每个不同特性来说(假设单个特性所给区间不重合),cnt[l]++和cnt[r+1]--的操作可以一起做完,最后求一次前缀和检查有没有sum[i]==m,有的话则该i就是对应奶牛的序号。
由于单个特性所给的区间也可能会重合,所以我这边直接打了个补丁处理了一下,先得到单个属性的tmp_sum[i]后,再分成独立的不重合的小区间,然后使用上面的算法。


全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐