百度20200903笔试思路分享
第一题，经典差分思路，不用对区间内每一个点加1。
差分模板: v[0] = a[0]; v[i] = a[i] = a[i-1];
如果对[l,r]区间内每个位置+1相当于v[l]++,v[r+1]--;
最后求个v的前缀和即为每一个位置的最终地毯层数。
附上代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T>0)
{
int L,n;
cin>>L>>n;
vector<int> v(L+2,0);
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
v[l]++;v[r+1]--;
}
for(int i=1;i<=L;i++)
{
v[i] += v[i-1];
if(i!=L)cout<<v[i]<<" ";
else cout<<v[i]<<endl;
}
T--;
}
return 0;
} 第二题，思路是贪心，代码就不列了，比较简单。 第三题，dfs超时，求大佬思路。
最终A了2.4。
#百度##笔试题型#
投递淘天集团等公司10个岗位 >