牛客代碼刷題記錄1

問題一

1. 給定一個數組序列, 需要求選出一個區間, 使得該區間是所有區間中經過如下計算的值最大的一個： 區間中的最小數 * 區間所有數的和最后程序輸出經過計算后的最大值即可，不需要輸出具體的區間。如給定序列 [6 2 1]則根據上述公式, 可得到所有可以選定各個區間的計算值:
   [6] = 6 * 6 = 36;
   [2] = 2 * 2 = 4;
   [1] = 1 * 1 = 1;
   [6,2] = 2 * 8 = 16;
   [2,1] = 1 * 3 = 3;
   [6, 2, 1] = 1 * 9 = 9;
   從上述計算可見選定區間 [6] ，計算值為 36，則程序輸出為 36。 區間內的所有數字都在[0, 100]的范圍內;

---

輸入輸出

• 輸入描述:
  第一行輸入點集的個數 N， 接下來 N 行，每行兩個數字代表點的 X 軸和 Y 軸。
  對于 50%的數據, 1 <= N <= 10000;
  對于 100%的數據, 1 <= N <= 500000;
• 輸出描述:
  輸出“最大的” 點集合， 按照 X 軸從小到大的方式輸出，每行兩個數字分別代表點的 X 軸和 Y軸。
• 輸入例子1:
  5
  1 2
  5 3
  4 6
  7 5
  9 0
• 輸出例子1:
  4 6
  7 5
  9 0

解決方案：

• 理解：
  如果x滿足P中任意點都不在x的右上方區域內（橫縱坐標都大于x），則稱其為“最大的”-> 不存在任何點其橫縱坐標都大于點x ->
• 分析：
  1.對所有點x軸進行降序排序，則第一個點一定是最大點
  2.后面的點要想成為最大點，只需其y值大于前面的最大的y值即可
  3.最后倒序輸出數組

if __name__ == "__main__":n = int(input())
# 二維數組輸入方式a = []for _ in range(n):  # ’_’作用同i，循環標志a.append(list(map(int, input().split())))a.sort(key=lambda x: x[0])j = len(a) - 2tmpy = a[-1][1]for i in range(len(a) - 1, -1, -1):if tmpy < a[i][1]:tmpy = a[i][1]a[j] = a[i]j -= 1for k in range(j + 1, len(a)):print(a[k][0], a[k][1])

函數/方法

• n=int(input(“[輸入]>”))
  input()返回是一個字符串,int(input())把input()返回的字符串轉換成整型,返回的是整型
• str.split(str="", num=string.count(str)
  #通過指定分隔符對字符串進行切片，如果參數 num 有指定值，則分隔 num+1 個子字符串,返回分割后的字符串列表。
  str = “Line1-abcdef \nLine2-abc \nLine4-abcd”;
  print str.split( ); # 默認以空格為分隔符，包含 \n \t
  print str.split(’ ', 1 ); # 以空格為分隔符，分隔成兩個
• map()
  根據提供的函數對指定序列做映射。map(function, iterable, …)，第一個參數 function 以參數序列中的每一個元素調用function函數，返回包含每次 function函數返回值的新列表。
  map(lambda x: x ** 2, [1, 2, 3, 4, 5]) # 使用 lambda 匿名函數
  [1, 4, 9, 16, 25]
• list()方法
  list(tuple) 將元組轉換為列表。
  注：元組與列表非常類似，區別在于元組的元素值不能修改，元組是放在括號()中，列表是放于方括號[]中。
  aTuple = (123, ‘runoob’, ‘google’, ‘abc’)
  aList = list(aTuple)
  print ("列表元素 : ")
  print(aList)
  列表元素 : [123, ‘runoob’, ‘google’, ‘abc’]
• list.sort()
  sort(cmp = None ,key = None, reverse = False) 函數用于對原列表進行排序，如果指定參數，則使用比較函數指定的比較函數。沒有返回值，但是會對列表的對象進行排序。
  cmp:可選參數, 如果指定了該參數會使用該參數的方法進行排序。
  key:可選參數，主要是用來進行比較的元素，只有一個參數，具體的函數的參數就是取自于可迭代對象中，指定可迭代對象中的一個元素來進行排序。
  reverse:排序規則，reverse = True 降序， reverse = False 升序（默認）。
  list.sorted()有返回值，返回對key值排好序的list

問題二

2. 給定一個數組序列, 需要求選出一個區間, 使得該區間是所有區間中經過如下計算的值最大的一個： 區間中的最小數 * 區間所有數的和最后程序輸出經過計算后的最大值即可，不需要輸出具體的區間。如給定序列 [6 2 1]則根據上述公式, 可得到所有可以選定各個區間的計算值:
   [6] = 6 * 6 = 36;
   [2] = 2 * 2 = 4;
   [1] = 1 * 1 = 1;
   [6,2] = 2 * 8 = 16;
   [2,1] = 1 * 3 = 3;
   [6, 2, 1] = 1 * 9 = 9;
   從上述計算可見選定區間 [6] ，計算值為 36，則程序輸出為 36。 區間內的所有數字都在[0, 100]的范圍內;

輸入輸出

• 輸入描述:
  第一行輸入數組序列長度n，第二行輸入數組序列。
  對于 50%的數據, 1 <= n <= 10000;
  對于 100%的數據, 1 <= n <= 500000;

• 輸出描述:
  輸出數組經過計算后的最大值。

• 輸入例子1:
  3
  6 2 1

• 輸出例子1:
  36

思路

遍歷每個數，并找出該數的最大區間，即該數在區間中最小，加總求積

if __name__ == "__main__":n = int(input())a = list(map(int, input().split()))ans = 0for i in range(n):tmp = a[i]l = r = iif tmp == 0:continuewhile l - 1 >= 0 and a[l - 1] >= tmp:l = l - 1while r + 1 < n and a[r + 1] >= tmp:r = r + 1ans= max(ans, tmp * sum(a[l: r + 1]))print(ans)

• continue 語句跳出本次循環，而break跳出整個循環。
  continue 語句用來告訴Python跳過當前循環的剩余語句，然后繼續進行下一輪循環，用在while和for循環中。