51nod 2500 后面第一个大于

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

小b有一个长度为n的序列t，现在她对于每个i，求最小的正数j满足i+j≤ni+j≤n且ti+j>titi+j>ti，输出j，如果不存在这样的j，则输出0。

样例解释：

对于i=1，t2>t1t2>t1，所以最小的j=1；

对于i=7，不存在这样的j，所以输出0。

收起

输入

第一行输入一个数n；
第二行输入n个数t1-tn，以空格隔开；
其中1≤n≤30000，对于任意ti满足30≤ti≤100.

输出

输出一行n个数，第i个数表示i的答案。

输入样例

8
73 74 75 71 69 72 76 73

输出样例

1 1 4 2 1 1 0 0暴力方法。
代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>using namespace std;
int n,t[];
int main() {
scanf("%d",&n);
for(int i = ;i < n;i ++) {
scanf("%d",&t[i]);
}
for(int i = ;i < n;i ++) {
if(i) putchar(' ');
for(int j = ;i + j < n;j ++) {
if(t[i + j] > t[i]) {
printf("%d",j);
break;
}
else if(i + j == n - ) printf("");
}
}
return ;
}

简单方法。

代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>using namespace std;
int n,t,ans[],m = ;
vector<int> ind[];
int main() {
scanf("%d",&n);
for(int i = ;i < n;i ++) {
scanf("%d",&t);
for(int j = m;j < t;j ++) {
for(int k = ind[j].size() - ;k >= ;k --) {
ans[ind[j][k]] = i - ind[j][k];
ind[j].pop_back();
}
}
m = min(m,t);
ind[t].push_back(i);
}
for(int i = ;i < n;i ++) {
if(i) putchar(' ');
printf("%d",ans[i]);
}
return ;
}