POJ 2796 Feel Good（并查集）

2024-03-30 06:08

文章标签 good poj 查集 2796 feel

本文主要是介绍POJ 2796 Feel Good（并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接思路：该题转化一下，就是枚举每一个数，找到以这个数为最小值的最大区间（因为没有负数）。那么一个办法是预处理出每一个数左边第一个比他大的数的位置，和右边第一个比他大的数的位置，这个可以用构造单调栈的线性算法处理出来：我们构造一个单调上升栈，标记栈里每个元素在实际中的位置，加入一个元素a[i]的时候，如果栈顶元素大于他，那么将栈顶元素出队列， i就是这个元素右边大于他的第一个元素。直到栈顶元素<=a[i]，这时，栈顶元素就是a[i]左边第一个>=他的，把a[i]入队列。复杂度O(n) 还有一个思维复杂度低的方法，我们从大到小访问每一个元素，如果他左边或者右边的元素>=他，他们将他们合并，这样，符合条件的集合就是一个连续区间。并且，先访问的一定>=后访问的，每次更新答案即可。

  typedef long long ll;  
 typedef long double ld;  
 const double eps = 1e-6;  
 const double PI = acos(-1);  
 const int mod = 1000000000 + 7;  
 const int INF = 0x3f3f3f3f;  
 const int seed = 131;  
 const ll INF64 = ll(1e18);  
 const int maxn = 1e5 + 10;  
 int T,n,m,p[maxn];  
 int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }  
 ll sum[maxn],a[maxn];  
 struct node {  
     int l, r, v;  
     node(int l=0, int r=0, int v=0):l(l), r(r), v(v) {}  
 }res[maxn];  
 struct edge {  
     int pos, v;  
     edge(int pos=0, int v=0):pos(pos), v(v) {}  
     bool operator < (const edge& rhs) const {  
         return v > rhs.v;  
     }  
 }b[maxn];  
 int main() {  
     while(~scanf("%d",&n)) {  
         ll ans = 0, l = 1, r = 1;  
         for(int i = 1; i <= n; i++) {  
             scanf("%I64d", &a[i]);  
             b[i] = edge(i, a[i]);  
             sum[i] = sum[i-1] + a[i];  
             p[i] = i;  
             res[i] = node(i, i, a[i]);  
             if(ans < a[i] * a[i]) {  
                 ans = a[i] * a[i];  
                 l = r = i;  
             }  
         }  
         sort(b+1, b+n+1);  
         for(int i = 1; i <= n; i++) {  
             int pp = b[i].pos;  
             if(pp > 1 && a[pp-1] >= a[pp]) {  
                 int x = _find(pp);  
                 int y = _find(pp-1);  
                 if(x != y) {  
                     p[x] = y;  
                     res[y] = node(min(res[y].l,res[x].l), max(res[y].r,res[x].r), a[pp]);  
                     if(ans < a[pp]*(sum[res[y].r] - sum[res[y].l-1])) {  
                         ans = a[pp]*(sum[res[y].r] - sum[res[y].l-1]);  
                         l = res[y].l;  
                         r = res[y].r;  
                     }  
                 }  
             }  
             if(pp < n && a[pp+1] >= a[pp]) {  
                 int x = _find(pp);  
                 int y = _find(pp+1);  
                 if(x != y) {  
                     p[x] = y;  
                     res[y] = node(min(res[y].l,res[x].l), max(res[y].r,res[x].r), a[pp]);  
                     if(ans < a[pp]*(sum[res[y].r] - sum[res[y].l-1])) {  
                         ans = a[pp]*(sum[res[y].r] - sum[res[y].l-1]);  
                         l = res[y].l;  
                         r = res[y].r;  
                     }  
                 }  
             }  
         }  
         printf("%I64d\n%I64d %I64d\n", ans, l, r);  
     }  
     return 0;  
 }  
 