A.张经理的员工
题意：求员工都到达两个工位中的某一个所需走的最短路径之和是多少
根据mid=(a+b)/2判断员工该往哪移，工位号小于等于mid的向a移动，大于mid的向b移动。
向a移动的又分为a左边右边（同b)
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; #define maxn 100002 int place[maxn]; int sum1[maxn]; int sum2[maxn]; int main(){ int n,q,i,j; int x; cin>>n>>q; for(i=1;i<=n;i++){ cin>>x; place[x]++; //求该工位号上的人数 } for(i=2;i<=maxn;i++){ sum1[i]=sum1[i-1]+place[i-1]*(i-1); //工位号小于i的员工的工位号的和 sum2[i]=sum2[i-1]+place[i-1]; //工位号小于i的员工的数量 } for(i=1;i<=q;i++){ int a,b; cin>>a>>b; if(a>b){ swap(a,b); } int mid=(a+b)/2; int ans=0; ans+=a*sum2[a]-sum1[a]; //a左边的一定比mid小 sum2[a]*(a-sum1[a]/sum2[a]) ans+=(sum1[mid+1]-sum1[a+1])-(sum2[mid+1]-sum2[a+1])*a; //a右边 (sum2[mid+1]-sum2[a+1])*((sum1[mid+1]-sum1[a+1])/(sum2[mid+1]-sum2[a+1])-a) ； ans+=(sum2[b]-sum2[mid+1])*b-(sum1[b]-sum1[mid+1]); // b左边 （sum2[b]-sum2[mid+1])*(b- (sum1[b]-sum1[mid+1])/(sum2[b]-sum2[mid+1])) ans+=sum1[maxn]-sum1[b+1]-(sum2[maxn]-sum2[b+1])*b; //b右边 （sum2[maxn]-sum2[b+1]）*((sum1[maxn]-aum1[b+1])/(sum2[maxn]-sum2[b+1])-b); cout<<ans<<endl; } return 0; }
B.随机序列
题意：求一串数的极差与方差
#include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int main(){ int t,n; int a[1010]; cin>>t; while(t--){ int dff=0,max=0,min=5000; double average=0,s=0,sum=0; memset(a,0,sizeof(a)); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; if(a[i]>max) max=a[i]; if(a[i]<min) min=a[i]; } dff=max-min; average=sum/n; for(int i=1;i<=n;i++){ s+=(a[i]-average)*(a[i]-average); } s=s/n; printf("%d %.3f\n",dff,s); } return 0; }