sdutacm-数据结构实验之栈五:下一较大值(一)

    xiaoxiao2021-03-26  7

    数据结构实验之栈五:下一较大值(一)

    TimeLimit: 1000MS Memory Limit: 65536KB

    SubmitStatistic

    Problem Description

    对于包含n1<=n<=1000)个整数的序列,对于序列中的每一元素,在序列中查找其位置之后第一个大于它的值,如果找到,输出所找到的值,否则,输出-1

    Input

     输入有多组,第一行输入t1<=t<=10),表示输入的组数;

    以后是 t 组输入:每组先输入n,表示本组序列的元素个数,之后依次输入本组的n个元素。

    Output

     输出有多组,每组之间输出一个空行(最后一组之后没有);

    每组输出按照本序列元素的顺序,依次逐行输出当前元素及其查找结果,两者之间以-->间隔。

    Example Input

    2

    4 12 2015 18

    5 20 1525 30 6

    Example Output

    12-->20

    20-->-1

    15-->18

    18-->-1

     

    20-->25

    15-->25

    25-->30

    30-->-1

    6-->-1

    Hint

     本题的数据量小、限时要求低,可以不用栈来完成。

    Author

    #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<stdlib.h> #include<stack> #define N 100100 using namespace std; struct node { int num,next,data; }; struct node a[N]; int main() { int t; scanf("%d",&t); stack<struct node>p; for(int i=1;i<=t;i++) { if(i>1)printf("\n"); while(!p.empty()) { p.pop(); } int n; scanf("%d",&n); for(int j=1;j<=n;j++) { scanf("%d",&a[j].data); a[j].num = j; a[j] .next = -1; if(p.empty()) { p.push(a[j]); } else { while(!p.empty()) { struct node b; b = p.top(); if(b.data<a[j].data) { a[b.num].next = a[j].data; p.pop(); } else break; } p.push(a[j]); } } for(int i=1;i<=n;i++) { printf("%d-->%d\n",a[i].data,a[i].next); } } return 0; } /*************************************************** User name: jk160505徐红博 Result: Accepted Take time: 0ms Take Memory: 156KB Submit time: 2017-01-13 15:14:21 ****************************************************/

    转载请注明原文地址: https://ju.6miu.com/read-600285.html

    最新回复(0)