17-比赛1 F - 较小元素 Weak in the Middle （set）

Seg-El has last chance to make the final changes in order to prevent the destruction of Krypton.

He is provided an array Arr[ ] of N elements.

For each element Arr [ i ], he needs to find the largest element Arr [ j ] where j < i and Arr [ j ] < Arr [ i ]

Help him to achieve this task.

Input

First line comprises N- the number of elements in the array.

Second line contains N space separated integers denoting the elements of the array.

Output

Print N lines denoting the required answer as specified above. In case no such value exists for some

Arr [ i ], print "-1" (without quotes).

Constraints

1 ≤ N ≤ 200000
1 ≤ Arr [ i ] ≤ 10¹⁵

Example

5
1 2 3 5 4

Output:

-1
1
2
3
3

通过 set 或 map 就可轻松解决；

关键字： set ，map , lower_bound()函数

1.学长的代码

 # include <bits/stdc++.h>

 using namespace std;

 set<long long> s;

 int main ()

 {

     int n;

     long long x;

     scanf("%d", &n);

     for (int i = ; i <= n; ++i) {

         scanf("%lld", &x);

         x = -x;

         auto iter = s.lower_bound(x + );

         if (iter == s.end()) puts("-1");

         else printf("%lld\n", -*iter);

         s.insert(x);

     }

     return ;

 }

2 . 一开始不会使用set ，用map自己做的

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     map<long long,int> imap;

     long long t;

     int n;

     cin>>n;

     for(int i =;i<=n;i++)

     {

         scanf("%lld",&t);

         t = -t;

         //map<long long,int>::iterator it;

         auto it = imap.lower_bound(t+);

         if(it == imap.end()) cout<<"-1"<<endl;

         else

            cout<<-(it->first)<<endl;

         imap[t] = i;

     }

     return ;

 }

巴特西

17-比赛1 F - 较小元素 Weak in the Middle （set）

Input

Output

Constraints

Example

最新文章

热门文章