一、链接
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:
3
1 10
5 5
10 1
输出样例1:
75 110 60
输入样例2:
3
2 1
1 2
2 1
输出样例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了
六、精美图片