目录
京东一个环，满足条件的对
猿题库 求出连续子数组之和为0
腾讯 区间二分[-90,90]
数组分成两个子数组，子数组和的差值绝对值最小 背包
数组分成两个子数组，子数组的平均值差值绝对值最大 排序
降序数组重排
#include<cstdio>
#include<queue>
using namespace std;
int a[1000010],n;
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
a[i]=n-i+1;
}
int i=1,j=n,k=0;
deque<int> q;
int res=0;
while(i<=j){
if(!k){
q.push_back(a[i]);
int sz=q.size();
res=max(res,sz);
a[i]=a[j];
i++,j--;
}else{
int top=q.front();
q.pop_front();
int tmp=a[i];
a[i]=top;
q.push_back(tmp);
int sz=q.size();
res=max(res,sz);
i++;
}
k=k^1;
}
if(a[i-1]==q.back()) q.pop_back();
while(!q.empty()){
if(!k){
int top=q.back();
q.pop_back();
a[i]=top;
i++,k=k^1;
}else{
int top=q.front();
q.pop_front();
a[i]=top;
i++,k=k^1;
}
}
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
}
时间复杂度O(n)，空间复杂度O(1)。
#include<cstdio>
using namespace std;
const int maxn=100010;
int n,a[maxn];
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
a[i]=n-i+1;
}
for(int i=1;i<=n;i++){
if(a[i]>n) continue;
else{
int k=i,j=-1,tmp=a[i]+n;
tmp-=n;
if(tmp>(n+1)/2) j=2*(n-tmp+1);
else j=2*tmp-1;
int num=a[j];
a[j]=tmp+n;
tmp=num+n;
k=j;
while(k!=i){
tmp-=n;
if(tmp>(n+1)/2) j=2*(n-tmp+1);
else j=2*tmp-1;
num=a[j];
a[j]=tmp+n;
tmp=num+n;
k=j;
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",a[i]-n);
}
printf("\n");
}
}
N*N矩阵求出M*M子矩阵的中位数（最大子矩阵和，最大全1子矩阵）
二维线段树？ http://blog.csdn.net/zxy_snow/article/details/6264135
http://blog.jobbole.com/98565/
