【藍橋杯python研究生組備賽】003 貪心

題目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)

知識點

  1. 主要是在于思路:任何多日間的低買高賣,都可以被簡化為每兩天之間的交易

題目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))

知識點

  1. 思路問題,首先是無疑是把貨倉建在 商店中間
  2. 當n為偶數,放在中間的兩個 中的一個
  3. 當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)    

知識點

糖果傳遞

  1. 圖例中的c1與代碼中的c1不是一致的
  2. c1-c4均可正可負
  3. 將問題轉化為,已知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
  • 按照右端點對區間進行排序,那么如果下一個需求坐標的左端點在 上一個坐標右端點的后面,則需要再放一個雷達,反之,不用放雷達
  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}')

知識點

貪心原則:局部考慮,當前某一個人距離最終均值最小:

  • 余額少于等于剩余的均值,那么付出所有余額
  • 余額大于剩余的均值,那么之后的所有人都大于該均值,每個人付出該均值
  1. 標準化輸出: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)

知識點

藍橋杯筆記:藍橋杯備賽筆記

  1. 主要是要考慮到所有的情況,做到不重復,不遺漏
  2. 首先是當n==k,那么就只能所有的數相乘
  3. k為偶數
    • 全正:排序后的數據,從右到左即可
    • 至少存在一個負數,此時k<n,那么就不選這個負數,剩下選擇成對的負數or正數,取絕對值最大的
  4. 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. 全是正數
    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)
  1. 全是負數
    -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)
  1. 有正有負
    -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 1n5000),表示服務點數量。

第二行輸入一個長度為 n n n 的二進制字符串 S S S1 表示當前服務點有志愿者,0 表示當前服務點無志愿者。

數據保證 S S S 至少包含 1 1 10

輸出格式

輸出一行若干個整數,表示每個無志愿者服務點到有志愿者服務點的最近距離,若不存在則輸出 ? 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=' ')

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/73161.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/73161.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/73161.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

網絡通信Socket中多態HandleIO設計模式深度解析

網絡通信 Socket 中多態 handleIO 詳細講解 大綱 引言 網絡通信的重要性Socket 編程在網絡通信中的地位多態 handleIO 的意義和作用 Socket 編程基礎 Socket 的基本概念Socket 的類型&#xff08;TCP 和 UDP&#xff09;Socket 編程的基本流程 多態的概念與實現 多態的定義和…

flutter 如何與原生框架通訊安卓 和 ios

在 Flutter 中與原生框架&#xff08;Android 和 iOS&#xff09;進行通信的主要方式是通過 **平臺通道&#xff08;Platform Channels&#xff09;**。平臺通道允許 Flutter 代碼與原生代碼進行雙向通信。以下是詳細的步驟和示例&#xff0c;說明如何在 Flutter 中與 Android …

LabVIEW VI Scripting實現連接器窗格自動化

通過VI Scripting自動化配置連接器窗格&#xff0c;可大幅提升開發效率、統一接口規范&#xff0c;并適配動態需求。以下為真實場景中的典型應用案例&#xff0c;涵蓋工業、汽車電子及教育領域&#xff0c;展示其實際價值與實施效果。 特點&#xff1a; 程序化配置&#xff1a;…

1-001:MySQL的存儲引擎有哪些?它們之間有什么區別?

MySQL 存儲引擎 ├── InnoDB&#xff08;默認引擎&#xff09; │ ├── 事務支持&#xff1a;支持 ACID 和事務&#xff08;事務日志、回滾、崩潰恢復&#xff09; │ ├── 鎖機制&#xff1a;支持行級鎖&#xff0c;提高并發性能 │ ├── 外鍵支持&#xff1a;支持外鍵…

package.json 依賴包約束及快速刪除node_modules

文章目錄 一、package.json版本約束1、初始項目安裝2. 已有 yarn.lock 文件的項目安裝3. 特殊情況手動修改 package.json 版本&#xff1a;使用 yarn upgrade 命令&#xff1a; 二、快速刪除node_modules三、depcheck 檢測npm未使用的依賴 一、package.json版本約束 1、初始項…

Redis Sentinel (哨兵模式)深度解析:構建高可用分布式緩存系統的核心機制

一、傳統主從復制的痛點 在分布式系統架構中&#xff0c;Redis 作為高性能緩存和數據存儲解決方案&#xff0c;其可用性直接關系到整個系統的穩定性。傳統的主從復制架構雖然實現了數據冗余&#xff0c;但在面臨節點故障時仍存在明顯缺陷&#xff1a; ?手動故障轉移&#xf…

[免費]微信小程序(圖書館)自習室座位預約管理系統(SpringBoot后端+Vue管理端)(高級版)【論文+源碼+SQL腳本】

大家好&#xff0c;我是java1234_小鋒老師&#xff0c;看到一個不錯的微信小程序(圖書館)自習室座位預約管理系統(SpringBoot后端Vue管理端)(高級版)&#xff0c;分享下哈。 項目視頻演示 【免費】微信小程序(圖書館)自習室座位預約管理系統(SpringBoot后端Vue管理端)(高級版…

微服務架構下的 Node.js

Node.js 在微服務架構中的特點 輕量級和高效性 Node.js 以其輕量級和高效的特點&#xff0c;非常適合構建微服務架構。它具有事件驅動和非阻塞 I/O 模型&#xff0c;能夠在處理高并發請求時表現出色。這意味著 Node.js 可以同時處理大量的并發連接&#xff0c;而不會因為阻塞…

Linux 配置靜態 IP

一、簡介 在 Linux CentOS 系統中默認動態分配 IP 地址&#xff0c;每次啟動虛擬機服務都是不一樣的 IP&#xff0c;因此要配置靜態 IP 地址避免每次都發生變化&#xff0c;下面將介紹配置靜態 IP 的詳細步驟。 首先先理解一下動態 IP 和靜態 IP 的概念&#xff1a; 動態 IP…

為什么 HTTP GET 方法不使用請求體?

本指南將揭示為什么 HTTP GET 方法不像其他 HTTP 方法那樣使用請求體&#xff0c;以及如何在 API 開發中有效地使用 GET 請求。 當談到 HTTP&#xff08;超文本傳輸協議&#xff09;時&#xff0c;您可能會好奇為什么 GET 方法通常不涉及請求體。在 Web 請求中&#xff0c;發送…

java后端--定時任務

定時任務 一、簡述二、注解1.Scheduled屬性&#xff1a; 2.EnableScheduling 三、案例 一、簡述 在java后端開發中&#xff0c;經常遇到一些任務需要頻繁發生&#xff0c;每次都人工調用太麻煩&#xff0c;這時就用到了定時任務進行自動化調用&#xff0c;大大便利了程序員的開…

JVM垃圾回收面試題及原理

1. 對象什么時候可以被垃圾器回收 如果一個或多個對象沒有任何的引用指向它了&#xff0c;那么這個對象現在就是垃圾&#xff0c;如果定位了垃圾&#xff0c;則有可能會被垃圾回收器回收 如果要定位什么是垃圾&#xff0c;有兩種方式來確定 引用計數法可達性分析算法 1.1 …

《Mycat核心技術》第19章:基于MySQL實現讀寫分離

作者&#xff1a;冰河 星球&#xff1a;http://m6z.cn/6aeFbs 博客&#xff1a;https://binghe.gitcode.host 文章匯總&#xff1a;https://binghe.gitcode.host/md/all/all.html 星球項目地址&#xff1a;https://binghe.gitcode.host/md/zsxq/introduce.html 沉淀&#xff0c…

【安卓逆向】安卓病毒介紹及其簡單案例分析

目錄 引言 一、Android 病毒介紹及分析方法 1.1 Android 病毒預覽 1.2 Android 病毒分析必備知識 1.3 Android 病毒的常見類型及惡意行為 1.3.1 常見病毒類型 1.3.2 常見病毒行為 1.4 病毒激活條件 1.5 Android 病毒的傳播方式 1.6 Android 病毒分析的一般方法 二…

基于LabVIEW的腳本化子VI動態生成

該示例展示了一種利用LabVIEW VI腳本&#xff08;VI Scripting&#xff09;技術&#xff0c;通過程序化方式動態生成并替換子VI的解決方案。核心邏輯為&#xff1a;基于預定義的模板VI&#xff0c;根據用戶選擇的數學操作&#xff08;加法或乘法&#xff09;&#xff0c;自動生…

機器學習之超參數優化(Hyperparameter Optimization)

超參數優化(Hyperparameter Optimization) 1. 簡介 在機器學習和深度學習中,超參數(Hyperparameters) 是在訓練之前需要設定的參數,例如學習率(learning rate)、批量大小(batch size)、神經網絡的層數等。與訓練過程中自動學習的模型參數(如權重和偏置)不同,超參…

Manus 演示案例:谷歌公司運營模擬器游戲體驗

一、項目背景與愿景 在科技行業蓬勃發展的當下&#xff0c;谷歌作為行業巨頭&#xff0c;其成長歷程充滿了無數值得深入探究的決策智慧。這些決策不僅塑造了谷歌的輝煌&#xff0c;也為全球企業的發展提供了寶貴的借鑒。本項目旨在打造一款以谷歌公司發展為藍本的運營模擬器游戲…

es-索引詳解

在 Elasticsearch 中&#xff0c;**索引&#xff08;Index&#xff09;**是核心概念之一&#xff0c;類似于關系型數據庫中的“表”。索引用于存儲、組織和檢索文檔&#xff08;Document&#xff09;。以下是關于 Elasticsearch 索引的詳細解析&#xff1a; 1. 索引的基本概念 …

基于策略模式的智能提示語生成器設計與實現——以Tkinter GUI開發為例

基于策略模式的智能提示語生成器設計與實現——以Tkinter GUI開發為例 一、引言&#xff1a;智能化時代的提示工程工具 在人工智能技術廣泛應用的時代背景下&#xff0c;如何與AI模型進行有效交互已成為關鍵技能。本文介紹的"AI任務需求與提示語策略生成器"正是基于…

01 | Go 項目開發極速入門課介紹

提示&#xff1a; 所有體系課見專欄&#xff1a;Go 項目開發極速入門實戰課。 你好&#xff0c;歡迎學習本課程。本課程是一個 Go 項目開發極速入門課程。旨在幫助剛學習完 Go 基礎語法的 Go 開發者&#xff0c;快速掌握如何開發一個功能相對全面的 Go 項目。 根據課程設計目標…