n=1e6，O(n*logn)还是能过的，数据规模小于2e7（1秒大概能跑2e7的数据）
#include <bits/stdc++.h> using namespace std; const int N=1e6+10; #define min3(a,b,c) min(min(a,b),c)//定义三个数的最小值 int n,x,k,cnt1,cnt2,ans,a[N],b[N]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin>>x; if(x>=0)a[++cnt1]=x;//a数组中储存正数 else b[++cnt2]=x;//b数组中储存负数 } sort(b+1,b+cnt2+1); ans=0x3f3f3f3f; for(int i=1;i<=cnt1;i++) { k=lower_bound(b+1,b+cnt2+1,-a[i])-b;//不是-b-1，而是直接-b if(k==cnt2+1){ans=min(ans,abs(a[i]+b[cnt2]));continue;} //如果在b数组中没有找到大于等于-a[i]的数，则k=cnt2+1，此时abs(a[i]+b[cnt2])最小 ans=min3(ans,abs(a[i]+b[k]),abs(a[i]+b[k-1])); } printf("%d\n",ans); return 0; }1、结构体数组排序做法。
#include <bits/stdc++.h> using namespace std; double ans; int n,sum; struct node { int x,num; }a[1010]; bool cmp(node s1,node s2) {return s1.x<s2.x;} int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].x; a[i].num=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) i==n?printf("%d\n",a[i].num):printf("%d ",a[i].num); for(int i=2;i<=n;i++) { sum+=a[i-1].x; ans+=sum; } printf("%.2lf\n",(double)ans/n); return 0; }2、优先队列做法。
掌握结构体优先队列自定义排序的写法：
struct node { int x,num; }; bool operator < (const node &s1,const node &s2)//重载运算符，自定义排序 { if(s1.x!=s2.x)return s1.x>s2.x;//与实际应该写的<号相反 else if(s1.num!=s2.num) return s1.num>s2.num;//与实际应该写的<号相反 //else if 这句排序很重要！(数组排序的时候默认有这句话，但是优先队列没有) } priority_queue<node>q;完整代码：
#include <bits/stdc++.h> using namespace std; double ans; int n,x,sum; struct node { int x,num; }; bool operator < (const node &s1,const node &s2) { if(s1.x!=s2.x)return s1.x>s2.x; else if(s1.num!=s2.num) return s1.num>s2.num; //else if 这句排序很重要！(数组排序的时候默认有这句话，但是优先队列没有) } priority_queue<node>q; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin>>x; q.push({x,i}); } for(int i=1;i<=n;i++) { i==n?printf("%d\n",q.top().num):printf("%d ",q.top().num); if(i<n){sum+=q.top().x;ans+=sum;} q.pop(); } printf("%.2lf\n",(double)ans/n); return 0; }容易想到O(n2)的暴力，也就是枚举所有可能的区间。数据规模达到1e8，显然TLE。(林大oj 1秒大概能跑2e7)
稍加优化，先求出所有区间内的最大值mx以及它对应的区间长度mxlen，当要查询的区间长度x<=mxlen时，区间可以取到最大值mx，直接输出答案。
当要查询的区间长度x>mxlen时，还是得O(n2)暴力…（所以我感觉优化得还不够彻底，但是还是过了…）
AC代码：
#include <bits/stdc++.h> using namespace std; const int N=1e4+10; int n,m,x,t,mx,cnt,tmp,mxlen,a[N],sum[N],ans[N]; int main() { ios::sync_with_stdio(false); cin>>n>>m; mx=-0x3f3f3f3f; for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i];//前缀和 if(tmp<0) { tmp=a[i]; cnt=1; } else { tmp+=a[i]; cnt++; } if(tmp>mx) { mx=tmp;//mx表示所有区间内的最大值 mxlen=cnt;//mxlen表示区间最大值mx对应的区间长度 } } memset(ans,-0x3f,sizeof(ans)); for(int k=mxlen+1;k<=n;k++)//枚举区间长度，其实也就是O(n^2)的暴力打表 for(int i=1;i<=n-k+1;i++)//枚举左端点i，右端点为i+k-1 ans[k]=max(ans[k],sum[i+k-1]-sum[i-1]); //ans[k]表示长度为k的所有区间中的最大值 while(m--) { cin>>x; if(x<=mxlen)printf("%d\n",mx);//x<=mxlen时，可以取到所有区间的最大值 else//其他情况则必须找最大值 { t=-0x3f3f3f3f; for(int i=x;i<=n;i++) t=max(t,ans[i]); printf("%d\n",t); } } return 0; }