某一天，n个朋友在一起聚会，他们已经很久没见了，于是他们决定拍照留念。
简单的说，拍照的时候，每个人有一个高度和宽度，第i个的高度和宽度分别是hi和wi。这些人排成一条直线，照片的最小的面积必须包含所有的的人，所以照片的面积是W*H，W是所有人的宽度之和，H是所有人中高度最高的那个人的高度。现在想要知道当第i个人不在照片中的时候，照片的最小面积是多少。
输入
第一行是一个正整数N，表示人的数量。
接下来N行，每行两个整数wi和hi，分别表示每个人的宽度和高度。
数据范围：2<=N<=200000,1<=wi<=10,1<=hi<=1000。
输出
包含b1，b2，b3。。Bn，bi表示第i个人不在照片中的时候，照片的最小面积。
输入输出样例
输入样例#1：
3
1 10
5 5
10 1
输出样例#1：
75 110 60
输入样例#2：
3
2 1
1 2
2 1
输出样例#2：
6 4 6
【思路1】
利用前缀和记录W 1~i的和 sum[i];
利用前后缀数组分别记录1~i(1≤i≤n)的最大值max1[i] 和i~1(1≤i≤n)的最大值max2[i];
处理第i个人时：W为 sum[n]-sum[i]+sum[i-1],H为max(max1[i-1],max2[i+1]);
相乘即可得出面积
代码：
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline int read()
{
char chr=getchar();
int f=1,ans=0;
while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)) {ans=ans*10;ans+=chr-'0';chr=getchar();}
return ans*f;
}
int n,w[200005] ,h[200005],sumw[200005],max1[200005],max2[200005];
int main()
{
n=read();
for(int i=1;i<=n;i++)
w[i]=read(),h[i]=read(),sumw[i]=sumw[i-1]+w[i];//前缀和
for(int i=1;i<=n;i++)//1~i最大值
max1[i]=max(max1[i-1],h[i]);
for(int i=n;i>=1;i--)n~i最大值
max2[i]=max(max2[i+1],h[i]);
for(int i=1;i<=n;i++)
{
int W=sumw[n]-sumw[i]+sumw[i-1];
int H=max(max1[i-1],max2[i+1]);//在左右两个区间分别取最大值；
printf("%d ",W*H);
}
return 0;
}
【思路2】
由于每次只有一个人出列，那么对于每个人来说，如果他是最高的，那么H就要取次高的，如果不是次高的，那么H就要取最高的，既然这样，只要记录最大值和次大值便可求出答案；
代码
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline int read()
{
char chr=getchar();
int f=1,ans=0;
while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)) {ans=ans*10;ans+=chr-'0';chr=getchar();}
return ans*f;
}
int n,w[200005] ,h[200005],sumw[200005],pos,max1=INT_MIN,max2=INT_MIN;
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
w[i]=read(),h[i]=read(),sumw[i]=sumw[i-1]+w[i];
if(max1<h[i])
pos=i,max1=h[i];
}
for(int i=1;i<=n;i++)
if(i!=pos)
max2=max(max2,h[i]);
for(int i=1;i<=n;i++)
{
int W=sumw[n]-sumw[i]+sumw[i-1];
int H;
if(h[i]==max1) H=max2;
else H=max1;
printf("%d ",W*H);
}
return 0;
}