題目1 股票買賣
給定一個長度為 N 的數組,數組中的第 i 個數字表示一個給定股票在第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。
注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。
輸入格式
第一行包含整數 N,表示數組長度。
第二行包含 N 個不大于 10000 的正整數,表示完整的數組。
輸出格式
輸出一個整數,表示最大利潤。
數據范圍
1≤N≤105
輸入樣例1:
6
7 1 5 3 6 4
輸出樣例1:
7
輸入樣例2:
5
1 2 3 4 5
輸出樣例2:
4
輸入樣例3:
5
7 6 4 3 1
輸出樣例3:
0
樣例解釋
樣例1:在第 2 天(股票價格 = 1)的時候買入,在第 3 天(股票價格 = 5)的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。隨后,在第 4 天(股票價格 = 3)的時候買入,在第 5 天(股票價格 = 6)的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。共得利潤 4+3 = 7。
樣例2:在第 1 天(股票價格 = 1)的時候買入,在第 5 天 (股票價格 = 5)的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票,之后再將它們賣出。因為這樣屬于同時參與了多筆交易,你必須在再次購買前出售掉之前的股票。
樣例3:在這種情況下, 不進行任何交易, 所以最大利潤為 0。
python代碼
n=int(input())
data=list(map(int,input().split()))ans=0for i in range(n-1):if data[i+1]>data[i]:ans+=data[i+1]-data[i]print(ans)
知識點
- 主要是在于思路:任何多日間的低買高賣,都可以被簡化為每兩天之間的交易
題目2 貨倉選址
在一條數軸上有 N 家商店,它們的坐標分別為 A1~AN。
現在需要在數軸上建立一家貨倉,每天清晨,從貨倉到每家商店都要運送一車商品。
為了提高效率,求把貨倉建在何處,可以使得貨倉到每家商店的距離之和最小。
輸入格式
第一行輸入整數 N。
第二行 N 個整數 A1~AN。
輸出格式
輸出一個整數,表示距離之和的最小值。
數據范圍
1≤N≤100000,
0≤Ai≤40000
輸入樣例:
4
6 2 9 1
輸出樣例:
12
python代碼
n=int(input())data=list(map(int,input().split()))
ans=0
data.sort()
if n%2==0:#n為偶數,選在中間兩個數中間place=data[n//2-1]
else:#n為奇數,選在中位數place=data[n//2]#計算總距離
for i in range(n):ans+=abs(data[i]-place)
print(int(ans))
知識點
- 思路問題,首先是無疑是把貨倉建在 商店中間
- 當n為偶數,放在中間的兩個 中的一個
- 當n為偶數,放在中間的一個
題目3 糖果傳遞
有 n 個小朋友坐成一圈,每人有 a[i] 個糖果。
每人只能給左右兩人傳遞糖果。
每人每次傳遞一個糖果代價為 1。
求使所有人獲得均等糖果的最小代價。
輸入格式
第一行輸入一個正整數 n,表示小朋友的個數。
接下來 n 行,每行一個整數 a[i],表示第 i 個小朋友初始得到的糖果的顆數。
輸出格式
輸出一個整數,表示最小代價。
數據范圍
1≤n≤1000000,
0≤a[i]≤2×10^9,
數據保證一定有解。
輸入樣例:
4
1
2
5
4
輸出樣例:
4
python代碼
n=int(input())
data=[0]
n1=n
while n1:a=int(input())data.append(a)n1-=1
ave=sum(data)//n
c=[0]*(n+1)for i in range(n):c[i+1]=c[i]+data[i]-ave
# print(c)
ans=0
c=[0]+sorted(c[1:n+1])
# print(c)
for i in range(1,n+1):#下標從1開始ans+=abs(c[i]-c[n//2+1])
print(ans)
知識點
- 圖例中的c1與代碼中的c1不是一致的
- c1-c4均可正可負
- 將問題轉化為,已知a1,a2,a3,a4,求距離每一個點 最小的距離和,而最優解就是中位數
題目4
假設海岸是一條無限長的直線,陸地位于海岸的一側,海洋位于另外一側。
每個小島都位于海洋一側的某個點上。
雷達裝置均位于海岸線上,且雷達的監測范圍為 d,當小島與某雷達的距離不超過 d 時,該小島可以被雷達覆蓋。
我們使用笛卡爾坐標系,定義海岸線為 x 軸,海的一側在 x 軸上方,陸地一側在 x 軸下方。
現在給出每個小島的具體坐標以及雷達的檢測范圍,請你求出能夠使所有小島都被雷達覆蓋所需的最小雷達數目。
輸入格式
第一行輸入兩個整數 n 和 d,分別代表小島數目和雷達檢測范圍。
接下來 n 行,每行輸入兩個整數,分別代表小島的 x,y 軸坐標。
同一行數據之間用空格隔開。
輸出格式
輸出一個整數,代表所需的最小雷達數目,若沒有解決方案則所需數目輸出 ?1。
數據范圍
1≤n≤1000,
1≤d≤200,
?1000≤x,y≤1000
輸入樣例:
3 2
1 2
-3 1
2 1
輸出樣例:
2
python代碼
n,d=map(int,input().split())data=[list(map(int,input().split())) for _ in range(n)]#先計算覆蓋每一個小島對應的線段
from math import sqrt
data.sort(key=lambda x:x[0])#按照橫坐標排序line=[]#存儲對應的線段for i in range(n):#如果小島縱坐標已經大于半徑,那么直接輸出-1if data[i][1]>d:print(-1)exit()elif data[i][1]==d:a,b=data[i][0],data[i][0]line.append([a,b])else:distance=sqrt(d**2-data[i][1]**2)a=data[i][0]-distanceb=data[i][0]+distanceline.append([a,b])line.sort(key=lambda x:x[1])#按照線段右端點排序
ans=0
last=line[0][1]#上一個雷達點for i in range(1,n):if last>=line[i][0]:ans+=0else:last=line[i][1]ans+=1
print(ans)
知識點
- 如果以雷達為核心,r為半徑的圓,去找覆蓋到的小島,不太容易判斷 那么就以小島為圓心,找到能滿足要求的 線段[a,b]
- 如果小島縱坐標已經大于半徑,那么直接輸出-1
- 按照右端點對區間進行排序,那么如果下一個需求坐標的左端點在 上一個坐標右端點的后面,則需要再放一個雷達,反之,不用放雷達
- 排序:
line.sort(key=lambda x:(x[1],x[0]))
:先按照line每一個元素的第二個值進行排序,若第二個值相等,按照這個元素的第一個值進行排序。
line=[[1,2],[3,2],[5,2],[-2,4]]
line.sort(key=lambda x:(x[1],x[0]))
print(line)#[[1, 2], [3, 2], [5, 2], [-2, 4]]
更多藍橋杯筆記:藍橋杯備賽筆記
題目5 付賬問題
幾個人一起出去吃飯是常有的事。
但在結帳的時候,常常會出現一些爭執。
現在有 n 個人出去吃飯,他們總共消費了 S 元。
其中第 i 個人帶了 ai 元。
幸運的是,所有人帶的錢的總數是足夠付賬的,但現在問題來了:每個人分別要出多少錢呢?
為了公平起見,我們希望在總付錢量恰好為 S 的前提下,最后每個人付的錢的標準差最小。
這里我們約定,每個人支付的錢數可以是任意非負實數,即可以不是 1 分錢的整數倍。
你需要輸出最小的標準差是多少。
標準差的介紹:標準差是多個數與它們平均數差值的平方平均數,一般用于刻畫這些數之間的“偏差有多大”。
形式化地說,設第 i 個人付的錢為 bi 元,那么標準差為 :
輸入格式
第一行包含兩個整數 n、S;
第二行包含 n 個非負整數 a1,?…,?an。
輸出格式
輸出最小的標準差,四舍五入保留 4 位小數。
數據范圍
1≤n≤5×105,
0≤ai≤109,
0≤S≤1015。
輸入樣例1:
5 2333
666 666 666 666 666
輸出樣例1:
0.0000
輸入樣例2:
10 30
2 1 4 7 4 8 3 6 4 7
輸出樣例2:
0.7928
python代碼
n,s=map(int,input().split())
data=list(map(int,input().split()))sum1=sum(data)
ave=s/nvar=0
data.sort()
i=0
while i<len(data):mean=s/nif data[i]<=mean:#余額小于均值,只能付出全部var+=(data[i]-ave)**2s-=data[i]n-=1i+=1else:#后面的每一個都大于當前均值var+=(mean-ave)**2*nbreak
var=(var/len(data))**0.5print(f'{var:.4f}')
知識點
貪心原則:局部考慮,當前某一個人距離最終均值最小:
- 余額少于等于剩余的均值,那么付出所有余額
- 余額大于剩余的均值,那么之后的所有人都大于該均值,每個人付出該均值
- 標準化輸出:
print(f'{var:.4f}')
:保留4位小數,浮點型
題目6 乘積最大
給定 N 個整數 A1,A2,…AN。
請你從中選出 K 個數,使其乘積最大。
請你求出最大的乘積,由于乘積可能超出整型范圍,你只需輸出乘積除以 1000000009 的余數。
注意,如果 X<0, 我們定義 X 除以 1000000009 的余數是負(?X)除以 1000000009 的余數,即:0?((0?x)%1000000009)
輸入格式
第一行包含兩個整數 N 和 K。
以下 N 行每行一個整數 Ai。
輸出格式
輸出一個整數,表示答案。
數據范圍
1≤K≤N≤10^5,
?10^5 ≤Ai≤ 10 ^5
輸入樣例1:
5 3
-100000
-10000
2
100000
10000
輸出樣例1:
999100009
輸入樣例2:
5 3
-100000
-100000
-2
-100000
-100000
輸出樣例2:
-999999829
python代碼
n,k=map(int,input().split())data=[int(input()) for _ in range(n)]
mod1=10**9+9def mod(x):if x>0:return x%mod1return -(-x%mod1)data.sort()
flag=1#標記是否全是負數
ans=1if k%2!=0:#奇數個,轉化為偶數問題ans*=data[-1]n-=1k-=1if data[-1]<0:#全是負數flag=-1l,r=0,n-1
while k:ll=data[l]*data[l+1]rr=data[r]*data[r-1]if ll*flag>=rr*flag:ans*=llans=mod(ans)l+=2else:ans*=rrans=mod(ans)r-=2k-=2print(ans)
知識點
藍橋杯筆記:藍橋杯備賽筆記
- 主要是要考慮到所有的情況,做到不重復,不遺漏
- 首先是當n==k,那么就只能所有的數相乘
- k為偶數
- 全正:排序后的數據,從右到左即可
- 至少存在一個負數,此時k<n,那么就不選這個負數,剩下選擇成對的負數or正數,取絕對值最大的
- k為奇數
- 全負:排序后的數據,從左到右即可,結果一定為負
- 至少存在一個正數,此時k<n,那么就選擇這個正數,之后從n-1個數中選擇k-1個(負數、正數都成對選),此時k-1為偶數,最終結果一定大于等于0
題目7 后綴表達式
給定 N 個加號、M 個減號以及 N+M+1 個整數 A1,A2,···,AN+M+1,小明想知道在所有由這 N 個加號、M 個減號以及 N+M+1 個整數湊出的合法的后綴表達式中,結果最大的是哪一個?
請你輸出這個最大的結果。
例如使用 123+?,則 “23+1?” 這個后綴表達式結果是 4,是最大的。
輸入格式
第一行包含兩個整數 N 和 M。
第二行包含 N+M+1 個整數 A1,A2,···,AN+M+1。
輸出格式
輸出一個整數,代表答案。
數據范圍
0≤N,M≤105,
?109≤Ai≤109
輸入樣例:
1 1
1 2 3
輸出樣例:
4
思路
藍橋杯筆記:藍橋杯備賽筆記
很多貪心題目一下子真的很難想出來,怎么辦?找規律
首先保證分類情況沒有重復沒有遺漏
- 全是正數
1 2 3 4 5
- n=4,m=0:全部相加
- n=3,m=1:5+4+3+2-1
- n=2,m=2:5+4+3-(1-2)
- n=1,m=3:5+4-(1-2-3)
- n=0,m=4:2-(1-5-4-3)
- 全是負數
-5 -4 -3 -2 -1
- n=4,m=0:全部相加
- n=3,m=1:(-1)-{(-5)+(-4)+(-3)+(-2)}
- n=2,m=2:(-1)-{(-5)+(-4)+(-3)}-(-2)
- n=1,m=3:(-1)-{(-5)+(-4)}-(-3)-(-2)
- n=0,m=4:(-1)-(-5)-(-4)-(-3)-(-2)
- 有正有負
-5 -4 -3 2 1
- n=4,m=0:全部相加
- n=3,m=1:(1)-{(-5)+(-4)+(-3)+(2)}
- n=2,m=2:(1)-{(-5)+(-4)}-(-3)+(2)
- n=1,m=3:(1)-{(-5)}-(-4)-(-3)+2
- n=0,m=4:(1)-(-5)-(-4)-(-3)-(-2)
不知道你找到規律沒?關鍵在于 減號的數量
- 減號數量為0,所有元素相加
- 減號數量不為0,列表中最大元素-最小元素+其余每一個元素的絕對值
import os
import sys
n,m=map(int,input().split())
data=list(map(int,input().split()))
data.sort()
ans=0
if m==0:#一個負號都不存在ans=sum(data)
else:#至少存在一個負號ans=data[-1]-data[0]for i in range(1,len(data)-1):ans+=abs(data[i])
print(ans)
題目8 社區服務
問題描述
為了慶祝婦女節,社區組織了一場“溫暖傳遞”活動。社區中有 n n n 個服務點排成一列,每個服務點可能有志愿者(用 1
表示)或暫時無人(用 0
表示)。
每個服務點都有居民需要幫助,現在你需要從左往右,為每個無志愿者服務點計算距離最近的有志愿者服務點的距離,若不存在則輸出 ? 1 -1 ?1。
輸入格式
第一行輸入一個整數 n n n( 1 ≤ n ≤ 5000 1 \leq n \leq 5000 1≤n≤5000),表示服務點數量。
第二行輸入一個長度為 n n n 的二進制字符串 S S S,1
表示當前服務點有志愿者,0
表示當前服務點無志愿者。
數據保證 S S S 至少包含 1 1 1 個 0
。
輸出格式
輸出一行若干個整數,表示每個無志愿者服務點到有志愿者服務點的最近距離,若不存在則輸出 ? 1 -1 ?1。
樣例輸入
7
1010100
樣例輸出
1 1 1 2
思路
一開始以為全是0,比如000,輸出一個“-1”,后來才知道正確答案是“-1 -1 -1”
記錄1的下標 對于每一個0,遍歷1的下標,更新1到0 的距離的最小值 如果最終這個最小值 找到了,就放進答案列表ans中 沒有找到這個最小值,即全是0的情況,把-1放進列表
python代碼
n=int(input())
data=list(map(int,input()))list_1=[]#存1的下標
for i in range(n):if data[i]==1:list_1.append(i)
ans=[]for i in range(n):ans1=nif data[i]==0:for j in list_1:ans1=min(ans1,abs(j-i))if ans1!=n:ans.append(ans)else:ans.append(-1)print(*ans,sep=' ')