百度笔试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]后，再分成独立的不重合的小区间，然后使用上面的算法。
投递京东等公司10个岗位
