题目：
小b有一个长度为n的序列t，现在她对于每个i，求最小的正数j满足𝑖+𝑗≤𝑛且𝑡𝑖+𝑗>𝑡𝑖，输出j，如果不存在这样的j，则输出0。
样例解释：
对于i=1，𝑡2>𝑡1，所以最小的j=1；
对于i=7，不存在这样的j，所以输出0。
输入
第一行输入一个数n；
第二行输入n个数t1-tn，以空格隔开；
其中1≤n≤30000，对于任意ti满足30≤ti≤100.
输出
输出一行n个数，第i个数表示i的答案。
输入样例
1
2
| 8
73 74 75 71 69 72 76 73
|
输出样例
解法：
用set记录ti出现的位置下标，在处理每个ti时，在大于ti的数中找到下标大于i并且i+j<n的最小值。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
set<int> s[110];
int a[30010];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
s[a[i]].insert(i);
}
for(int i = 1; i <= n; i++){
bool flag = false;
int ans = 30010;
for(int j = a[i] + 1; j <= 100; j++){
if(s[j].upper_bound(i) != s[j].end()){
int p = *s[j].upper_bound(i);
//printf("%d\n",p);
flag = true;
ans = min(ans,p - i);
}
}
if(!flag)
printf("0 ");
else
printf("%d ",ans);
}
return 0;
}
|