藍橋杯 19. 最大比例

最大比例

原題目鏈接

題目描述

X 星球的某個大獎賽設了 M 級獎勵。每個級別的獎金是一個正整數。

并且,相鄰兩個級別間的比例是一個固定值,也就是說:所有級別的獎金構成一個等比數列

例如:
獎金數列為 16, 24, 36, 54,其等比值為 3/23/23/2

現在,我們隨機調查了一些獲獎者的獎金數。
請你根據這些數據推算出可能的最大等比值


輸入描述

  • 第一行:一個整數 N0 < N < 100),表示接下來有 N 個正整數;
  • 第二行:N 個正整數 X?, X?, ..., X?X? < 10?),用空格隔開,表示調查到的某些獲獎者的獎金數額。

輸出描述

  • 輸出一個形如 A/B 的最簡分數,表示可能的最大比例系數,其中 AB 是互質正整數。

輸入樣例

3
1250 200 32

輸出樣例

25/4

c++代碼

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll greatest_common_divisor(ll a, ll b) {if (a < b) return greatest_common_divisor(b, a);if (b == 0) return a;else return greatest_common_divisor(b, a % b);
}int main() {ll n, a, maxi, maxj;cin >> n;vector<double> arr;double min_val = DBL_MAX;unordered_set<ll> st;for (ll i = 0; i < n; i++) {cin >> a;if (st.find(a) == st.end()) {st.insert(a);arr.push_back(a);}}sort(arr.begin(), arr.end());for (ll i = 1; i < arr.size(); i++) {if (arr[i] / arr[i - 1] < min_val) {maxi = (ll)arr[i - 1];maxj = (ll)arr[i];min_val = arr[i] / arr[i - 1];}}ll k = greatest_common_divisor(maxi, maxj);cout << maxj / k<< "/" << maxi / k;return 0;
}//by wqs

思路解析

貪心做法是,排序+去重后,選擇相鄰兩個數比值最小的。

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

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

相關文章

基于 Python 的自然語言處理系列(82):Transformer Reinforcement Learning

&#x1f517; 本文所用工具&#xff1a;trl、transformers、peft、bitsandbytes &#x1f4d8; 官方文檔參考&#xff1a;https://huggingface.co/docs/trl 一、引言&#xff1a;從有監督微調到 RLHF 全流程 隨著語言大模型的發展&#xff0c;如何在大規模預訓練模型基礎上更精…

JAVA猜數小游戲

import java.util.Random; import java.util.Scanner;public class HelloWorld {public static void main(String[] args) {Random rnew Random();int luck_number r.nextInt(100)1;while (true){System.out.println("輸入猜數字");Scanner sc new Scanner(System…

GPU渲染階段介紹+Shader基礎結構實現

GPU是什么 &#xff08;CPU&#xff09;Center Processing Unit:邏輯編程 &#xff08;GPU&#xff09;Graphics Processing Unit&#xff1a;圖形處理&#xff08;矩陣運算&#xff0c;數據公式運算&#xff0c;光柵化&#xff09; 渲染管線 渲染管線也稱為渲染流水線&#x…

Spring Boot + MyBatis 動態字段更新方法

在Spring Boot和MyBatis中&#xff0c;實現動態更新不固定字段的步驟如下&#xff1a; 方法一&#xff1a;使用MyBatis動態SQL&#xff08;適合字段允許為null的場景&#xff09; 定義實體類 包含所有可能被更新的字段。 Mapper接口 定義更新方法&#xff0c;參數為實體對象&…

單例模式:確保唯一實例的設計模式

單例模式&#xff1a;確保唯一實例的設計模式 一、模式核心&#xff1a;保證類僅有一個實例并提供全局訪問點 在軟件開發中&#xff0c;有些類需要確保只有一個實例&#xff08;如系統配置類、日志管理器&#xff09;&#xff0c;避免因多個實例導致狀態混亂或資源浪費。 單…

UnoCSS原子CSS引擎-前端福音

UnoCSS是一款原子化的即時按需 CSS 引擎&#xff0c;其中沒有核心實用程序&#xff0c;所有功能都是通過預設提供的。默認情況下UnoCSS應用通過預設來實現相關功能。 UnoCSS中文文檔&#xff1a; https://www.unocss.com.cn 前有很多種原子化的框架&#xff0c;例如 Tailwind…

【Qwen2.5-VL 踩坑記錄】本地 + 海外賬號和國內賬號的 API 調用區別(阿里云百煉平臺)

API 調用 阿里云百煉平臺的海內外 API 的區別&#xff1a; 海外版&#xff1a;需要進行 API 基礎 URL 設置國內版&#xff1a;無需設置。 本人的服務器在香港&#xff0c;采用海外版的 API 時&#xff0c;需要進行如下API端點配置 / API基礎URL設置 / API客戶端配置&#xf…

C語言筆記(鵬哥)上課板書+課件匯總(結構體)-----數據結構常用

結構體 目錄&#xff1a; 1、結構體類型聲明 2、結構體變量的創建和初始化 3、結構體成員訪問操作符 4、結構體內存對齊*****&#xff08;重要指數五顆星&#xff09; 5、結構體傳參 6、結構體實現位段 一、結構體類型聲明 其實在指針中我們已經講解了一些結構體內容了&…

UV: Python包和項目管理器(從入門到不放棄教程)

目錄 UV: Python包和項目管理器&#xff08;從入門到不放棄教程&#xff09;1. 為什么用uv&#xff0c;而不是conda或者pip2. 安裝uv&#xff08;Windows&#xff09;2.1 powershell下載2.2 winget下載2.3 直接下載安裝包 3. uv教程3.1 創建虛擬環境 (uv venv) 4. uvx5. 此pip非…

網絡開發基礎(游戲方向)之 概念名詞

前言 1、一款網絡游戲分為客戶端和服務端兩個部分&#xff0c;客戶端程序運行在用戶的電腦或手機上&#xff0c;服務端程序運行在游戲運營商的服務器上。 2、客戶端和服務端之間&#xff0c;服務端和服務端之間一般都是使用TCP網絡通信。客戶端和客戶端之間通過服務端的消息轉…

java將pdf轉換成word

1、jar包準備 在項目中新增lib目錄&#xff0c;并將如下兩個文件放入lib目錄下 aspose-words-15.8.0-jdk16.jar aspose-pdf-22.9.jar 2、pom.xml配置 <dependency><groupId>com.aspose</groupId><artifactId>aspose-pdf</artifactId><versi…

【C/C++】插件機制:基于工廠函數的動態插件加載

本文介紹了如何通過 C 的 工廠函數、動態庫&#xff08;.so 文件&#xff09;和 dlopen / dlsym 實現插件機制。這個機制允許程序在運行時動態加載和調用插件&#xff0c;而無需在編譯時知道插件的具體類型。 一、 動態插件機制 在現代 C 中&#xff0c;插件機制廣泛應用于需要…

【音視頻】AAC-ADTS分析

AAC-ADTS 格式分析 AAC?頻格式&#xff1a;Advanced Audio Coding(?級?頻解碼)&#xff0c;是?種由MPEG-4標準定義的有損?頻壓縮格式&#xff0c;由Fraunhofer發展&#xff0c;Dolby, Sony和AT&T是主 要的貢獻者。 ADIF&#xff1a;Audio Data Interchange Format ?…

機器學習 Day12 集成學習簡單介紹

1.集成學習概述 1.1. 什么是集成學習 集成學習是一種通過組合多個模型來提高預測性能的機器學習方法。它類似于&#xff1a; 超級個體 vs 弱者聯盟 單個復雜模型(如9次多項式函數)可能能力過強但容易過擬合 組合多個簡單模型(如一堆1次函數)可以增強能力而不易過擬合 集成…

通過爬蟲方式實現頭條號發布視頻(2025年4月)

1、將真實的cookie貼到代碼目錄中toutiaohao_cookie.txt文件里,修改python代碼里的user_agent和video_path, cover_path等變量的值,最后運行python腳本即可; 2、運行之前根據import提示安裝一些常見依賴,比如requests等; 3、2025年4月份最新版; 代碼如下: import js…

Linux ssh免密登陸設置

使用 ssh-copy-id 命令來設置 SSH 免密登錄&#xff0c;并確保所有相關文件和目錄權限正確設置&#xff0c;可以按照以下步驟進行&#xff1a; 步驟 1&#xff1a;在源服務器&#xff08;198.120.1.109&#xff09;生成 SSH 密鑰對 如果還沒有生成 SSH 密鑰對&#xff0c;首先…

《讓機器人讀懂你的心:情感分析技術融合奧秘》

機器人早已不再局限于執行簡單機械的任務&#xff0c;人們期望它們能像人類伙伴一樣&#xff0c;理解我們的喜怒哀樂&#xff0c;實現更自然、溫暖的互動。情感分析技術&#xff0c;正是賦予機器人這種“理解人類情緒”能力的關鍵鑰匙&#xff0c;它的融入將徹底革新機器人與人…

Linux筆記---進程間通信:匿名管道

1. 管道通信 1.1 管道的概念與分類 管道&#xff08;Pipe&#xff09; 是進程間通信&#xff08;IPC&#xff09;的一種基礎機制&#xff0c;主要用于在具有親緣關系的進程&#xff08;如父子進程、兄弟進程&#xff09;之間傳遞數據&#xff0c;其核心特性是通過內核緩沖區實…

Ollama API 應用指南

1. 基礎信息 默認地址: http://localhost:11434/api數據格式: application/json支持方法: POST&#xff08;主要&#xff09;、GET&#xff08;部分接口&#xff09; 2. 模型管理 API (1) 列出本地模型 端點: GET /api/tags功能: 獲取已下載的模型列表。示例:curl http://lo…

【OSCP-vulnhub】Raven-2

目錄 端口掃描 本地/etc/hosts文件解析 目錄掃描&#xff1a; 第一個flag 利用msf下載exp flag2 flag3 Mysql登錄 查看mysql的運行權限 MySql提權&#xff1a;UDF 查看數據庫寫入條件 查看插件目錄 查看是否可以遠程登錄 gcc編譯.o文件 創建so文件 創建臨時監聽…