这个题目会做的很偶然，突然想到的，因为我们要求离这只海象的最远的比他年轻的海象，这个年轻的海象可以用单调栈维护。
就是从前往后遍历一遍，单调栈里面存年龄从小往大的海象，这个为什么这么存呢，因为如果后面有比这个队列里面更年轻的海象，
那么就可以更新，而且这个更新是正确的，不会有影响，这个可以自己想一想/
然后就可以得到一个单调栈的数组，这个时候因为单调栈是单调的，所以可以用二分来查找我们所需要的值。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;
typedef long long ll;
int queue_min[maxn];
int f1 = , t1 = , r = ;
int ans[maxn];
ll num[maxn];
ll a[maxn]; int ok(ll s)
{
int x = , y = t1;
int mid = (x + y) / ;
while(x<=y)
{
mid = (x + y) / ;
if (a[queue_min[mid]] >= s) y = mid-;
else x = mid + ;
//printf("x=%d y=%d mid=%d\n",x,y, mid);
}
//printf("mid=%d queue_min=%d\n", mid, queue_min[mid]);
if (a[queue_min[mid]] >= s) return queue_min[mid - ];
return queue_min[mid];
} int main()
{
int n;
scanf("%d", &n);
f1 = , t1 = , r = ;
for (int i = ; i <= n; i++) scanf("%lld", &a[i]);
queue_min[] = ;
while(r<n)
{
r++;
while (f1 <= t1 && a[r] < a[queue_min[t1]]) t1--;
queue_min[++t1] = r;
}
for (int i = f1; i <= t1; i++) {
num[i] = a[queue_min[i]];
// printf("queue_min[%d]=%d\n", i, queue_min[i]);
// printf("num[%d]=%lld\n", i, num[i]);
}
for(int i=;i<=n;i++)
{
int f = ok(a[i]);
//printf("F=%d\n",f);
if (f < i) ans[i] = -;
else ans[i] = f - i - ;
printf("%d ", ans[i]);
}
printf("\n");
return ;
}
单调栈 海象
这个题目和上面那个其实是一样的，但是我居然没有发现，这个要先前缀和处理一下，然后你就发现其实求的就是 比如 i ，求的就是 i 后面的比 i 更大的sum的最远位置。
也是二分+单调队列
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e6 + ;
typedef long long ll;
int queue_max[maxn];
int a[maxn], num[maxn];
ll sum[maxn];
int f1, t1;
int r; int ok(ll s) {
int x = , y = t1;
int mid = (x + y) / ;
while (x <= y) {
mid = (x + y) / ;
if (sum[queue_max[mid]] > s) x = mid + ;
else y = mid - ;
//printf("x=%d y=%d mid=%d\n", x, y, mid);
}
//printf("mid=%d queue_min=%d\n", mid, queue_min[mid]);
if (sum[queue_max[mid]] <= s) return queue_max[mid - ];
return queue_max[mid];
} int main() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%lld", &sum[i]);
sum[i] += sum[i - ];
// printf("sum[%d]=%lld\n", i, sum[i]);
}
f1 = , t1 = ;
r = ;
queue_max[] = ;
int ans = ;
while (r <= n) {
while (t1 >= f1 && sum[r] > sum[queue_max[t1]]) t1--;
queue_max[++t1] = r;
//printf("queue_max[%d]=%d\n", t1, queue_max[t1]);
r++;
}
for (int i = f1; i <= t1; i++) {
num[i] = sum[queue_max[i]];
//printf("queue[%d]=%d\n", i, queue_max[i]);
}
for (int i = ; i <= n; i++) {
int f = ok(sum[i]);
//printf("i=%d f=%d\n", i, f);
if (f > i)
{
if (sum[i] >= ) ans = max(ans, f - i + );
else ans = max(ans, f - i);
}
}
printf("%d\n", ans);
return ;
}
二分+单调队列