acwing第 115 场周赛第二题题解：维护最大值和次大值

一、链接

5132. 奶牛照相

二、题目

约翰的农场有 nn 头奶牛，编号 1∼n1∼n。

其中，第 ii 头奶牛的宽度为 wiwi，高度为 hihi，

有一天，它们聚餐后决定拍照留念。

关于拍照的描述如下：

它们一共拍了 nn 张照片，其中第 ii 张照片由第 ii 头奶牛给其它所有奶牛拍摄，即照片中包含除了奶牛 ii 以外的所有奶牛。
在拍照时，所有被拍摄的奶牛站成一排，拍出的照片呈矩形。
每张照片的尺寸大小为 W×HW×H，其中 WW 为照片中所有奶牛的宽度之和，HH 为照片中最高的奶牛的高度。

请你计算并输出每张照片的面积（W×HW×H 的值）。

输入格式

第一行包含整数 nn，表示共有 nn 头奶牛。

接下来 nn 行，其中第 ii 行包含两个整数 wi,hiwi,hi，表示第 ii 头奶牛的宽度和高度。

输出格式

输出共一行，nn 个整数，其中第 ii 个整数表示第 ii 张照片的面积。

注意，第 ii 张照片包含除了奶牛 ii 以外的所有奶牛。

数据范围

前 33 个测试点满足 2≤n≤32≤n≤3。
所有测试点满足 2≤n≤2×1052≤n≤2×105，1≤wi≤101≤wi≤10，1≤hi≤10001≤hi≤1000。

输入样例1：

输出样例1：

75 110 60

输入样例2：

输出样例2：

6 4 6

三、题意

去除某一个元素，其他元素的宽度求和，高度取最大值，输出乘积

四、代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=2e5+10;

int w[N],h[N];

int main()
{
    int n,sum=0,h1=0,h2=0,res=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)    
    {
        scanf("%d%d",&w[i],&h[i]);
        sum+=w[i];
        if(h[i]>h1) h2=h1,h1=h[i];
        else if(h[i]>h2)    h2=h[i];
    }
    
    for(int i=0;i<n;i++)
    {
        if(h[i]==h1)
        {
            res=(sum-w[i])*h2;
        }
        else
        {
            res=(sum-w[i])*h1;
        }
        printf("%d ",res);
    }
    
    return 0;
}

五、总结

1.不要单纯的模拟，不是很熟练，单纯的模拟比较难以实现，要想办法怎么写能达到同样的要求

2.求和比较简单，先求出所有元素宽度的和，然后每一个循环减去当前元素的宽度，就是去除当前元素的和

3.求去除一个元素之后的高度的最大值，有两种情况，第一种情况，去除的元素的高度是最大值（针对所有元素来说），那么就需要使用次大值（所有元素的次大值），第二种情况，去除的元素的高度不是最大值（针对所有元素来说），就使用最大值即可

4.在初始化阶段求出高度的最大值和次大值：次大值小于等于最大值，可以把数轴分成三个区间，第一个区间是遍历的元素大于最大值，把次大值更新为原来的最大值，把最大值更新成当前遍历的元素；第二个区间是在次大值和最大值之间，最大值不变，次大值更新为当前元素；第三个区间是当前元素小于次大值，最大值和次大值不需要进行修改。

5.输出结果这道题就完美的ac了

六、精美图片

文章来源地址https://uudwc.com/A/2Y5zy