首页 > ACM题库 > 九度OJ > 九度-1422-Closest Number[数据结构]
2014
01-19

九度-1422-Closest Number[数据结构]

里面来自九度:第四届ACM_DIY群程序设计竞赛

http://ac.jobdu.com/problem.php?pid=1422

题目描述:
        There is one Master In ACM_DIY called “白衣少年”(White) whose motto is “I can HOLD ANY FEMALE”. Since White is really busy with HOLDING FEMALES, he has no idea of the work that is given by his boss(MALE, of course), so can you help him to solve such a simple and really easy problem:Array A has N positive integers,for each A[i] (0<=i<N, indicating the i-th integer in the array A), it fits in a 32-bit signed integer ),find the closest number less than A[i] (if the distance is the same,we prefer the left one).

If you can solve this problem, White may give you some “tips”(You know better!)

 

输入:
        T cases (1<=T<=5)For each case, the first line give an integer N(1<= N <= 10^6),then the second line has the array with N integers. (All the integers are guaranteed to fit in 32-bit signed integer)

 

输出:
        For each case, print one line with N space-seperated integers, where the i-th integer is the number who is less that A[i] and is closest to i if exists, otherwise it is 0. 

样例输入:
3
3
2 1 3
3
2 3 1
4
5 7 3 6
样例输出:
1 0 1
1 2 0
3 5 0 3

思路:

1.从左往右遍历,维护一个索引结构的记录数组R[],和一个索引结构升序栈S[],依次压入A[i],同时A[i]左侧的closet number记录R[]为栈顶索引元素,
2.从右往左遍历,可以继续用1中的栈S[],也可以重新做另一个升序栈SS[],然后按照1的过程从右往左遍历,比较R[]和S[];

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
const int NUM=1000001;
int AA[NUM]={0};
struct Rec
{
    int value;
    int idx;
}R[NUM],S[NUM];
int main()
{
    int n;
    int num;
    //设置栈0元素。
    int top=0;
    S[top].value=0;
    S[top].idx =0;
    cin>>n;
    for(int i=0;i<n;i++)
    {    
        cin>>num;
        for(int i=1;i<=num;i++)
        {
            cin>>AA[i];
            R[i].value=0;
            R[i].idx=0;
        }
        top=0;
        for(int i=1;i<=num;i++)
        {
            //出栈
            while(  AA[i]<=S[top].value )
                top--;
            R[i] =S[top];
            //入栈
            top++;
            S[top].value=AA[i];
            S[top].idx=i;
        }
        top=0;
        for(int i=num;i>0;i--)
        {
            //出栈
            while(  AA[i]<=S[top].value )
                top--;            
            if( (top>0)&&((R[i].value ==0)||((i-R[i].idx)>(S[top].idx-i))))
                R[i]=S[top];
            //入栈
            top++;
            S[top].value=AA[i];
            S[top].idx=i;
        }
        for(int i=1; i<num;i++)
            cout<<R[i].value << " ";
        cout<<R[num].value;
        cout<<endl;
    }//for
    return 0;
}