首页 > 代码库 > UVa1619 Feel Good (标记,枚举)

UVa1619 Feel Good (标记,枚举)

2024-08-14 10:48:09   216人阅读

链接：http://vjudge.net/problem/UVA-1619

 

分析：首先计算前缀和，后面会用到。设每个i都属于一个满足下述条件的最大区间（因为题意说是正整数序列，区间当然越大越好），a[i]为区间中的最小值，然后预处理出以i为轴向左和向右延伸的最远位置L[i]和R[i]来标记这个区间，最后就是O（n）的枚举。

 

 1 #include <cstdio> 2  3 const int maxn = 1e5+5; 4  5 int n, a[maxn], L[maxn], R[maxn]; 6 long long prefix_sum[maxn]; 7  8 int main() { 9     int T = 0;10     while (scanf("%d", &n) == 1) {11         if (T++) printf("\n");12         a[0] = -1; a[n+1] = -1; prefix_sum[0] = 0;13         for (int i = 1; i <= n; i++) {14             scanf("%d", &a[i]);15             prefix_sum[i] = prefix_sum[i-1] + a[i];16             L[i] = i; R[i] = i;17         }18         for (int i = 1; i <= n; i++)19             while (a[i] <= a[L[i]-1]) L[i] = L[L[i]-1];20         for (int i = n; i >= 1; i--)21             while (a[i] <= a[R[i]+1]) R[i] = R[R[i]+1];22         long long ans = a[1] * a[1];23         int l = 1, r = 1;24         for (int i = 1; i <= n; i++) {25             long long v = (prefix_sum[R[i]] - prefix_sum[L[i]-1]) * a[i];26             if (v > ans || (v == ans && r-l > R[i]-L[i])) {27                 ans = v;28                 l = L[i], r = R[i];29             }30         }31         printf("%lld\n", ans);32         printf("%d %d\n", l, r);33     }34     return 0;35 }

 

UVa1619 Feel Good (标记,枚举)


联系
我们