东莞建网站公司动,大理网站制作,网页制作素材 期末考试,如何在网上推广二维码正题
题目链接#xff1a;http://poj.org/problem?id3784 题目大意
给出n个数#xff0c;每两个数输出一次到目前为止输入了的所有数的中位数。 解题思路
我们使用离线算法。 既然这是一个一个输入#xff0c;那么我们就用秘技时光倒流之数。先把所有数加入进去#x…正题
题目链接http://poj.org/problem?id3784 题目大意
给出n个数每两个数输出一次到目前为止输入了的所有数的中位数。 解题思路
我们使用离线算法。 既然这是一个一个输入那么我们就用秘技·时光倒流之数。先把所有数加入进去然后在两个两个删除。 先排一个序然后再用一个链表以便O(1)O(1)O(1)时间复杂度midmidmid指针左右移动的时候不会移动到已经删除过的。之后我们每次删除就用删除掉的数很目前的中位数比较然后在左右移动midmidmid指针 code
#includecstdio
#includealgorithm
using namespace std;
struct rec{int val,id;bool operator(const rec x)const{return valx.val;}
}a[10005];
int t,num,n,f[10005],pre[10005],nex[10005],mid,ans[10005],cnt;
int main()
{freopen(data.txt,w,stdout);scanf(%d,t);for(int ti1;tit;ti){cnt0;scanf(%d%d,num,n);midn11;printf(%d %d\n,num,mid);for(int i1;in;i)scanf(%d,a[i].val),a[i].idi;stable_sort(a1,a1n);//排序nex[0]1;pre[n1]n;for(int i1;in;i)f[a[i].id]i,pre[i]i-1,nex[i]i1;//建立链表for(int in;;i-2){ans[cnt]a[mid].val;//记录答案if(i1) break;if(f[i]midf[i-1]mid)midpre[mid];else if(f[i]midf[i-1]mid)midnex[mid];//指针移动nex[pre[f[i]]]nex[f[i]];pre[nex[f[i]]]pre[f[i]];pre[nex[f[i-1]]]pre[f[i-1]];nex[pre[f[i-1]]]nex[f[i-1]];//删除元素}int k0;for(int icnt;i;i--)//倒着输出{printf(%d ,ans[i]);k;if(k10||i1) k0,printf(\n);}}
}
