题解 CF522B 【Photo to Remember】

亿堆人排队拍照，然后每个人出去一下，问除了出去的人，队伍的最大面积是多少

模拟题

思路：

一个变量记录除了出队的人的总宽度，一个变量记录最高的人的高度

错误代码：

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        if(j!=i)
        {
            maxn=max(maxn,H[i]);
            ans+=W[i];
        }
    }
    printf("%d ",ans*maxn);
}

此代码会TLE！！！

不能读入完了后输出答案时一个个查找最高的，不然会TLE！

为此，我们只能在输入时做点功夫，一个变量在输入时加进所有人的宽度，再开一个数组，记录高

接着，把新开的newH数组从大到小快排（有点懒，直接用了函数），在输出时用

(总宽度-当前出队的人的宽度)*当前最高的身高

但是，问题来了，题目中没说数据不重复，可能会有两个最高的人高度相等

解决方法：

不用考虑，因为快排并不会去重，及时当前这个人是最高的，第二高的就在他n-1的地方，因此，照常做就行

code：

#include <cstdio>
#include <algorithm>
using namespace std;
int n,W[200001],H[200001],newH[200001],ans,maxn;    //newH记录高度
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&W[i],&H[i]);
        ans+=W[i];  //在输入时加进所有高度
        newH[i]=H[i];   //newH记录
    }
    sort(newH+1,newH+n+1);  //把newH数组排序，从而得出最高的
    for(int i=1;i<=n;i++)
    {
        int x=ans-W[i];     //总宽度-当前出队的人的宽度
        if(H[i]!=newH[n])   //如果当前出队的人不是最高的那个
            printf("%d ",x*newH[n]);    //输出当前宽度*最高的高度
        else    //如果目前一个是最高的
            printf("%d ",x*newH[n-1]);  //输出当前宽度*第二高的
    }
    return 0;
}