CCF最大的矩形（简单模拟）

78 阅读 0 评论 52 点赞

我是靠谱客的博主可靠小熊猫，这篇文章主要介绍CCF最大的矩形（简单模拟），现在分享给大家，希望可以做个参考。

思路：
存好图后，对于每一个矩形都一其为起点从左和从右遍历一次
记录下大于或等于它的数量（必须是连续的，不然就break掉）
然后求出每个矩形的最大值
最后再和所有矩形的最小值*n作比较取最大值即为答案
AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;
#define LL long long
string s ;
LL arr[1050] ;
int main(){
  int n ;
  cin >> n ;
  LL ans = 0 ;
  for(int i = 0 ;i < n ; i++) cin >> arr[i] ;
  for(int i = 0 ; i < n ; i++){
             LL coun = 1 ;
     for(int j = i-1 ; j >=0 ; j--){
        if(arr[j] >= arr[i] ) coun++ ;
        else {  break ; }
     }
    // ans = max(ans , coun * arr[i]) ;
   //  coun = 1 ;
     for(int j = i+1 ; j < n ; j++){
        if(arr[j] >= arr[i] ) coun++ ;
        else  break ;
     }
     ans = max(ans , coun * arr[i]) ;
  }
 //  cout << ans << endl ;

  LL mix = 9699 ;
  for(int i = 0 ; i < n ; i++){
     mix = min(mix , arr[i]) ;
  }
  cout << max(ans , mix*n) << endl  ;
  return 0 ;
}