四道编程题,三道100%,第四道没看
第一题:
#include <iostream> using namespace std; int main() { string str; cin>>str; int n=str.size(); int sum1=0; int sum2=0; for(int i=0;i<n;i++) { if(str[i]=='0') sum2+=1; else sum2+=2; } int result=sum1+sum2; for(int i=0;i<n;i++) { if(str[i]=='0') sum1+=2,sum2-=1; else sum1+=1,sum2-=2; result=max(result,sum1+sum2); } cout<<result<<endl; return 0; }第二道
#include <iostream> #include <vector> #include <stdio.h> using namespace std; int main() { vector<int> input; char ch=' '; while(ch!='\n') { int temp; cin>>temp; input.push_back(temp); scanf("%c",&ch); } int n=input.size(); int result=0; for(int i=0;i<n;i++) { if(input[i]==1) continue; int left=0; int j; for(j=i-1;j>=0;j--) { if(input[j]==1) break; else left++; } if(j<0 || i==0) left=2000; int right=0; for(int j=i+1;j<n;j++) { if(input[j]==1) break; else right++; } if(j>=n || i==n-1) right=2000; result=max(result,min(left,right)); } cout<<result+1<<endl; return 0; }第三道:迪杰特斯拉算法
#include <iostream> #include <set> using namespace std; int main() { int n,k,m; cin>>n>>k>>m; int **mat=new int*[n+1]; for(int i=0;i<n+1;i++) mat[i]=new int[n+1]; for(int i=0;i<n+1;i++) for(int j=0;j<n+1;j++) mat[i][j]=0; for(int i=0;i<m;i++) { int v,u,w; cin>>v>>u>>w; mat[v][u]=w; } int* cost=new int[n+1]; for(int i=1;i<n+1;i++) { if(mat[k][i]==0) cost[i]=-1; else cost[i]=mat[k][i]; } cost[k]=0; set<int> xv; for(int i=1;i<n+1;i++) xv.insert(i); xv.erase(k); while(1) { if(xv.size()==0) break; int index=-1; for(set<int>::iterator ite=xv.begin();ite!=xv.end();ite++) { if(cost[*ite]==-1) continue; if(index==-1) { index=*ite; continue; } if(cost[*ite]<cost[index]) index=*ite; } if(index==-1) break; xv.erase(index); for(set<int>::iterator ite=xv.begin();ite!=xv.end();ite++) { if(mat[index][*ite]==0) continue; if(cost[*ite]==-1) { cost[*ite]=cost[index]+mat[index][*ite]; continue; } if(cost[*ite]>cost[index]+mat[index][*ite]) cost[*ite]=cost[index]+mat[index][*ite]; } } int result=-1; for(int i=1;i<n+1;i++) { if(cost[i]==-1) { cout<<"-1"<<endl; return 0; } if(result==-1) result=cost[i]; else result=max(result,cost[i]); } cout<<result<<endl; return 0; }
全部评论
(2) 回帖