字节跳动笔试题100-0-80-0，第二道 期末考试怎么做啊
第一题，前后两次遍历就可以了
#include<bits/stdc++.h>
using namespace std;
#define N 1000009
char c[N];
int ans[N];
int main(){
int n;
cin>>n;
cin>>c;
for(int i=0;i<n;i++) ans[i] = N;
int temp=-1;
for(int i=0;i<n;i++){
if(c[i]=='O'){
ans[i] = 0;
temp = i;
}else{
if(temp==-1) continue;
ans[i] = min(i-temp,ans[i]);
}
}
temp = -1;
for(int i=n-1;i>=0;i--){
if(c[i]=='O'){
temp = i;
}else{
if(temp==-1) continue;
ans[i] = min(ans[i],temp-i);
}
}
for(int i=0;i<n;i++){
if(i!=0) cout<<" ";
cout<<ans[i];
}
cout<<endl;
return 0;
} 第二题，我觉得应该类似最大子序列和，但是一直 0分。。。
f[i]记录前i道题最多能答几道（且必须包含第i道）
t[i]记录的是 前i道 答f[i]道所需的最少时间。
然后就是用线性动态规划的思想去算，，感觉思路没啥问题 但是一直0分，
查了特别久 也没看出问题，，心态就有点小蹦
#include<bits/stdc++.h>
using namespace std;
#define N 1009
#define ll long long
ll a[N],f[N],t[N];
int main(){
int T,n,m;
cin>>T;
while(T--){
cin>>n>>m;
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++) cin>>a[i];
f[0] = t[0] = 0;
for(int i=1;i<=n;i++){
f[i] = 0;
for(int j=0;j<i;j++){
if((t[j]+a[i])<=m){
if((f[j]+1)>f[i]){
f[i] = f[j]+1;
t[i] = a[i]+t[j];
}else if((f[j]+1)==f[i]){
t[i] = min(t[j]+a[i],t[i]);
}
}
}
}
for(int i=1;i<=n;i++){
if(i!=1) cout<<" ";
cout<<i-f[i];
}
if(T!=0)
cout<<endl;
}
return 0;
} 第三题，感觉就是拓扑排序，然后用优先队列 保证序号小的领导先输出。
但是只有80分，，不知道哪里有坑。
#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define ll long long
int a[N][N],in[N];
void getInt(char*s,vector<int>& v){
v.clear();
int num = 0;
for(int i=0;s[i];i++){
if(s[i]==' '){
v.push_back(num);
num = 0;
}else{
num = num*10+s[i]-'0';
}
}
v.push_back(num);
}
char str[100000];
int main(){
int i,j,n=0,x,cur;
memset(a,0,sizeof(a));
memset(in,0,sizeof(in));
vector<int> ans,v;
while(gets(str)!=NULL){
// all++;
getInt(str,v);
for(i=0;i<v.size();i++) n = max(n,v[i]);
x = v[0];
for(i=1;i<v.size();i++){
a[v[i]][x] = 1;
in[x]++;
}
}
// n = all;
priority_queue <int,vector<int>,greater<int> > q;
for(i=1;i<=n;i++) if(in[i]==0) q.push(i);
while(!q.empty()){
cur = q.top(); q.pop();
ans.push_back(cur);
for(i=1;i<=n;i++){
if(i==cur||a[cur][i]==0) continue;
in[i]--;
if(in[i]==0) q.push(i);
}
}
if(ans.size()!=n){
cout<<-1<<endl;
}else{
// cout<<"n="<<n<<endl;
for(i=0;i<ans.size();i++){
if(i!=0) cout<<" ";
cout<<ans[i];
}
cout<<endl;
}
return 0;
} 第四题，因为第二题一直没找出问题，后面就没时间做了
看了一眼就放掉了。。。
有没有人分享下，第二题和第三题啊
投递OPPO等公司10个岗位