//第一题 #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; int a[maxn],b[maxn]; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; bool flag=1; int ans=0; for(int i=1;i<=n;++i)cin>>a[i]; for(int i=1;i<=n;++i)cin>>b[i]; int id=-1; for(int i=1;i<=n;++i){ if(a[i]!=b[i]){ if(a[i]>b[i])flag=0; else ans=b[i]-a[i]; id=i; break; } } for(int i=id+1;i<=n;++i){ if(a[i]+ans!=b[i]){ for(int j=i;j<=n;j++)if(a[j]!=b[j])flag=0; break; } } if(!flag)puts("NO"); else puts("YES"); } return 0; }
第二题
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; int val[maxn],res1[maxn],res2[maxn]; int arr[maxn]; int main() { int n; cin>>n; for(int i=0;i<n;++i)cin>>val[i]; long long int ans=0; for(int i=n-2;i>=0;--i){ if(val[i+1]>=val[i])continue;; int t = (val[i]-1)/val[i+1]; ans+=t; val[i]/=(t+1); } cout<<ans; return 0; }第三题
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; int a[maxn],b[maxn]; int n,m; int fin(int x){ int l = 0,r = n+1; for(int i=0;i<50;++i){ int mid=(l+r)/2; if(a[mid]>x)r=mid; else l=mid; } return l; } int main() { // int n,m; cin>>n>>m; for(int i=1;i<=n;++i)scanf("%d",&a[i]); for(int i=1;i<=m;++i)scanf("%d",&b[i]); sort(a+1,a+1+n); sort(b+1,b+1+m); long long int ans(0); for(int i=1;i<=m;++i){ int id = fin(b[i]); ans+=b[i]-a[id]; } cout<<ans; return 0; }
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+5; int val[maxn],res[maxn],res2[maxn]; int arr[maxn]; pair<int,int>skt[maxn]; int main() { int t; cin>>t; while(t--){ int n;cin>>n; for(int i=1;i<=n;++i)cin>>val[i]; int top=0; for(int i=1;i<=n;++i){ while(top&&skt[top].first<=val[i])--top; if(top){ res[i]=i-skt[top].second-1; } else { res[i]=i-1; } ++top; skt[top]=make_pair(val[i],i); } for(int i=1;i<=n;i++)skt[i].first=skt[i].second=0; top=0; for(int i=n;i>=1;--i){ while(top&&skt[top].first<=val[i])--top; if(top){ res[i]+=skt[top].second-i-1; } else res[i]+=(n-i); skt[++top]=make_pair(val[i],i); } for(int i=1;i<=n;i++)cout<<res[i]<<' '; puts(""); } return 0; }
全部评论
(2) 回帖