POJ-2082-Terrible Sets

秒速五厘米 2022-01-10 05:11 146阅读 0赞

### 链接：https://vjudge.net/problem/POJ-2082\#author=0 ###

### 题意： ###

挨个给n个矩形的宽和高，求内部矩形的最大面积

### 思路： ###

单调栈，每次tmp记录出栈的总宽度。记录到下一次出栈要增加的宽度。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <queue>
    #include <string>
    #include <stack>
    
    using namespace std;
    
    typedef long long LL;
    
    const int MAXN = 5e4 + 10;
    
    struct Squere
    {
        int _w;
        int _h;
    }squ[MAXN];
    
    int main()
    {
        int n;
        while (scanf("%d", &n))
        {
            if (n == -1)
                break;
            for (int i = 1;i <= n;i++)
                scanf("%d%d", &squ[i]._w, &squ[i]._h);
            stack<Squere> r;
            int res = 0;
            for (int i = 1;i <= n;i++)
            {
                int tmp = 0;
                while (!r.empty() && r.top()._h > squ[i]._h)
                {
                    Squere f = r.top();
                    r.pop();
                    res = max(res, f._h * (f._w + tmp));
                    squ[i]._w += f._w;
                    tmp += f._w;
                }
                r.push(squ[i]);
            }
            while (!r.empty())
            {
                Squere f = r.top();
                r.pop();
                res = max(res, f._h * f._w);
                if (!r.empty())
                    r.top()._w += f._w;
            }
            printf("%d\n", res);
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10606792.html

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关母函数+例题（hdu 2079+hdu 2082）

母函数+例题（hdu 2079+hdu 2082）虽然ACM的确有点力不从心，但是还是贵在坚持，继续啃啃算法。。。。。昨天一个下午学了学母函数，离散数学+幂级数，只

待我称王封你为后i/ 2023年06月10日 09:28/ 0 赞/ 104 阅读

相关 HDU 2082-找单词（母函数-有限次）

找单词 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

快来打我*/ 2022年09月25日 01:24/ 0 赞/ 71 阅读

相关 poj 2296 Map Labeler【二分+2-set】【经典】

题目：[poj 2296 Map Labeler][] 题意：给出以下二维坐标点，然后让你往平面上放正方形，点必须落在正方形上面边的中点或者下面边的中点，正方形不能重叠，可以

谁践踏了优雅/ 2022年08月08日 12:56/ 0 赞/ 102 阅读

相关 HDU 2082 找单词

HDU 2082 找单词：[http://acm.hdu.edu.cn/showproblem.php?pid=2082][http_acm.hdu.edu.cn_showpr

桃扇骨/ 2022年07月28日 01:55/ 0 赞/ 178 阅读

相关 Arpa’s obvious problem and Mehrdad’s terrible solution

![Center][]![Center 1][] 思路：此题考察了异或运算符，自己做的比较拙，用sign标记出现的数的次数，然后从头遍历，将x的两个异或因子的sign相乘，

Love The Way You Lie/ 2022年06月12日 11:59/ 0 赞/ 150 阅读

相关 HDU 2082 找单词[母函数]

找单词 Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

今天药忘吃喽~/ 2022年05月30日 12:42/ 0 赞/ 179 阅读

相关 hdu 2082 - 找单词

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=2082][http_acm.hdu.edu.cn_showproblem.p

Bertha 。/ 2022年05月28日 13:24/ 0 赞/ 158 阅读

相关 hdu 2082

include <iostream> include <math.h> include <stdio.h> include <string.h>

柔光的暖阳◎/ 2022年05月28日 13:06/ 0 赞/ 165 阅读

相关 POJ-2082-Terrible Sets

链接：https://vjudge.net/problem/POJ-2082\author=0 题意：挨个给n个矩形的宽和高，求内部矩形的最大面积思路：

秒速五厘米/ 2022年01月10日 05:11/ 0 赞/ 147 阅读

相关 POJ - 2082 - Terrible Sets【单调队列】题解

目录 1.题目 2.代码 1.题目 Let N be the set of all natural numb

红太狼/ 2021年07月25日 02:01/ 0 赞/ 386 阅读