Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
为什么超内存 ,用链表写的线段树,,求解//why memory exceed??? #include<iostream> using namespace std; const int N=1000000; int n, k, a[N]; struct Node { short mx, mn; struct Node *lc, *rc; /*Node() { lc = NULL; rc = NULL; }*/ } *mx; void creatmx(Node *&p, int &ii, int &jj) { if(ii>jj) return; p = new Node; p->lc = NULL; p->rc = NULL; if(ii==jj) p->mx = p->mn = a[ii]; else { int x; int mid = (ii+jj)/2; creatmx(p->lc, ii, mid); x = mid+1; creatmx(p->rc, x, jj); p->mx = __max(p->lc->mx, p->rc->mx); p->mn = __min(p->lc->mn, p->rc->mn); } } int findm(Node *&p, int &ii, int &jj, int &k, int &l) { if(ii==k && jj==l) return p->mx; else { int mid = (ii + jj)/2; if(l<=mid) return findm(p->lc, ii, mid, k, l); else if(k>mid) { int x = mid+1; return findm(p->rc, x, jj, k, l); } else// if(k<=mid && l>=mid) { int x = mid+1; int m1 = findm(p->lc, ii, mid, k, mid); int m2 = findm(p->rc, x, jj, x, l); if(m1 > m2) return m1; else return m2; } } } /* void creatmn(Node *&p, int ii, int jj) { if(ii>jj) return; p = new Node; if(ii==jj) p->mx = a[ii]; else { int mid = (ii+jj)/2; creatmn(p->lc, ii, mid); creatmn(p->rc, mid+1, jj); p->mx = __min(p->lc->mx, p->rc->mx); } } */ int findm1(Node *&p, int &ii, int &jj, int &k, int &l) { if(ii==k && jj==l) return p->mn; else { int mid = (ii + jj)/2; if(l<=mid) return findm1(p->lc, ii, mid, k, l); else if(k>mid) { int x = mid+1; return findm1(p->rc, x, jj, k, l); } else// if(k<=mid && l>=mid) { int x = mid+1; int m1 = findm1(p->lc, ii, mid, k, mid); int m2 = findm1(p->rc, x, jj, x, l); if(m1 < m2) return m1; else return m2; } } } int main() { int i, st, en, ii, jj; scanf("%d%d", &n, &k); for(i=0; i<n; i++) scanf("%d", &a[i]); st = 0; en = n-1; creatmx(mx,st, en); for(i=0; i<n-k; i++) { ii=i,jj=i+k-1; printf("%d ", findm1(mx, st, en, ii, jj)); } ii = n-k, jj = n-1; printf("%d\n", findm1(mx, st, en, ii, jj)); for(i=0; i<n-k; i++) { ii = i, jj=i+k-1; printf("%d ", findm(mx, st, en, ii, jj)); } ii = n-k, jj=n-1; printf("%d\n", findm(mx, st, en, ii, jj)); return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator