FilesExpand file tree

 master

/

code2.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (59 loc) · 1.41 KB

 master

/

code2.cpp

Top

File metadata and controls

• Code
• Blame

64 lines (59 loc) · 1.41 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

#include <stdio.h>

#include <vector>

#include <string>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

using namespace std;

//有一块矩形土地被划分成 N×M 个正方形小块，每块是一平方米。这些小块高低不平，

//每一小块地都有自己的高度H(i, j)米。水可以由任意一块地流向周围四个方向的四块地中，

//但不能直接流入对角相连的小块中。一场大雨后，许多低洼地方都积存了不少降水，求出它最多能积存多少立方米的降水么?

int trap(int* a, int n)

{

if ( a == NULL || n == 0 )

return 0;

int* left = new int[n];

if ( left == NULL )

return 0;

int* right = new int[n];

if ( right == NULL )

return 0;

int maxL = 0;

for ( int i = 0 ; i < n-1; i++ )

{

left[i] = maxL;

maxL = max(maxL, a[i]);

}

int maxR = 0;

for ( int i = n-1; i >= 0; i-- )

{

right[i] = maxR;

maxR = max(maxR, a[i]);

}

int res = 0;

for ( int i = 0 ; i < n-1 ;i++)

{

int v = min(left[i], right[i]) - a[i];

if ( v > 0 )

res += v;

}

delete[] left;

delete[] right;

return res;

}