CF1898B Milena and Admirer(貪心)

題目鏈接

題目大意

有一個長度為 n 的數組
做操作使這個數組不遞減:

  • 把一個數分成兩個數,例如:x 分為 a 和 b, x == a + b

求最小操作次數

思路

見注釋

代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];signed main()
{int T;cin >> T;while (T -- ){int n; cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];int ans = 0;for (int i = n - 1; i >= 1; i -- ) {if (a[i] > a[i + 1]){int x = a[i] / a[i + 1]; //分成幾個數 if (a[i] % a[i + 1] != 0) x ++; //如果有余數,那就多分出了一個數a[i]  = a[i] / x; //使分成的那幾個數的最小值盡可能大,就取一下平均值// 例如//a[i]  = 13, a[i + 1] = 3//直接除后的方法使我們知道需要分成5個數字://1, 3, 3, 3, 3//但是1太小了,會影響a[i - 1] //要使它變大,就讓13 / 5, 取平均值//得到 2, 2, 2, 2, 2, 余3,多的3就放在最后三位//即 2, 2, 3, 3, 3,//因為相當于是把多的往少的勻,所以絕對不會影響到a[i + 1] ,即最大值不會超過a[i + 1] ans += (x - 1);// x是分成的數的個數,x - 1就是需要的步驟數}}cout << ans << endl; }return 0;
}

總結

復述一遍思路:
當前面的數比后面的數大時,就需要拆分這個數,拆成盡可能少的個數,每個數還要盡可能大,這些數取決于后一個數,當前數 除以后一個數,如果能整除,那就分為那么多個數,且是最大的,若不能,則會多分出一個數,要使它們盡可能大(最小值最大),就是要讓那個余數最大,但余數肯定大不過除數,就把這個數平均分為這么多個數,多出來的就平均分配進分出來的每一個數里面,實現最大化最小值的操作。

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

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

相關文章

Shutter的安裝及使用

概要&#xff1a;本篇主要講述截圖軟件Shutter的安裝和使用&#xff0c;操作系統是Ubuntu22.04 一、安裝 sudo apt install shutter 二、區域截圖 1、打開Shutter&#xff0c;點擊Selection 2、提示信息 3、框選矩形區域 按住鼠標左鍵&#xff0c;拖動鼠標&#xff0c;松…

IT行業最被低估的六項技術,再加上一項尚未消亡的技術

2023年&#xff0c;生成式人工智能——更具體地說是ChatGPT——吸引了業界的廣泛關注&#xff0c;深得董事會、首席執行官和其他高管的一致贊賞&#xff08;也不乏害怕情緒&#xff09;。當然&#xff0c;他們的熱情是有道理的&#xff0c;多項研究發現&#xff0c;人工智能正在…

Electron[4] Electron最簡單的打包實踐

1 背景 前面三篇已經完成通過Electron搭建的最簡單的HelloWorld應用了&#xff0c;雖然這個應用還沒添加任何實質的功能&#xff0c;但是用來作為打包的案例&#xff0c;足矣。下面再分享下通過Electron-forge來將應用打包成安裝包。 2 依賴 在Electron[2] Electron使用準備…

[山東大學操作系統課程設計]實驗四+實驗五

0.寫在前面&#xff1a; 為什么這次把兩個實驗放在一起寫了&#xff0c;因為實驗五的要求就是在實驗四的基礎上完成實現的。但是我得實現說明&#xff0c;我的實驗四雖然完成了要求&#xff0c;但是無法在我自己的實驗四的基礎上完成實驗五&#xff0c;這是一個很大的問題&…

軟考考前背過-軟件設計師

今年5月份開始準備考&#xff0c;沒想到會突然改革&#xff0c;還好刷題刷的多&#xff0c;也過了。 跟著B站up主的視頻學的&#xff0c;都學了一遍之后才開始刷題&#xff0c;平時要上班&#xff0c;也就下班和周末能學&#xff0c;時間可能拉的比較長&#xff0c;學完前面的內…

使用linux CentOS本地部署SQL Server數據庫

&#x1f308;個人主頁&#xff1a;聆風吟 &#x1f525;系列專欄&#xff1a;數據結構、Cpolar雜談 &#x1f516;少年有夢不應止于心動&#xff0c;更要付諸行動。 文章目錄 &#x1f4cb;前言一. 安裝sql server二. 局域網測試連接三. 安裝cpolar內網穿透四. 將sqlserver映射…

【注冊測繪師備考——1.中華人民共和國測繪法】

學習一下《中華人民共和國測繪法》原始網址如下 《中華人民共和國測繪法》 中華人民共和國測繪法 &#xff08;1992年12月28日第七屆全國人民代表大會常務委員會第二十九次會議通過 2002年8月29日第九屆全國人民代表大會常務委員會第二十九次會議第一次修訂 2017年4月27日…

【Vulnhub 靶場】【Funbox: GaoKao】【簡單】【20210606】

1、環境介紹 靶場介紹&#xff1a;https://www.vulnhub.com/entry/funbox-gaokao,707/ 靶場下載&#xff1a;https://download.vulnhub.com/funbox/FunboxGaoKao.ova 靶場難度&#xff1a;簡單 發布日期&#xff1a;2021年06月06日 文件大小&#xff1a;1.3 GB 靶場作者&#…

[BJDCTF2020]EzPHP 許多的特性

這道題可以學到很多東西 靜下心來慢慢通過本地知道是干嘛用的就可以學會了 BJDctf2020 Ezphp_[bjdctf2020]ezphp-CSDN博客 這里開始 一部分一部分看 $_SERVER[QUERY_SRING]的漏洞 if($_SERVER) { if (preg_match(/shana|debu|aqua|cute|arg|code|flag|system|exec|passwd|…

Windows 上安裝nvm node版本管理工具 windows安裝nvm 管理工具

Windows 上安裝nvm node版本管理工具 windows安裝nvm 管理工具 1、nvm2、安裝2.1、下載 NVM 安裝程序進行安裝2.2、打開nvm的安裝路徑&#xff0c;運行終端測試是否安裝成功2.3、配置環境變量&#xff0c;讓nvm能在電腦全局使用2.3.1、nvm配置淘寶鏡像2.3.2、nvm環境變量設置 1…

低代碼還是好用的,我持有這個觀念

低代碼開發是近年來迅速崛起的軟件開發方法&#xff0c;讓編寫應用程序變得更快、更簡單。 有人說它是美味的膳食&#xff0c;讓開發過程高效而滿足&#xff0c;但也有人質疑它是垃圾食品&#xff0c;缺乏定制性與深度。 你認為低代碼到底是美味的膳食還是垃圾食品呢&#xff0…

SQL數據庫-客觀題 復習

一.單選 2.學校新開發了一個系統&#xff0c;通過收集與分析學生的學習行為&#xff0c;對其進行精準畫像&#xff0c;進而提供個性化的學習策略&#xff0c;這屬于________系統。 答案&#xff1a;D 知識點&#xff1a;【32010200】 知識考核要求&#xff1a;【3】 能力考…

C++ 模擬實現vector

目錄 一、定義 二、模擬實現 1、無參初始化 2、size&capacity 3、reserve 4、push_back 5、迭代器 6、empty 7、pop_back 8、operator[ ] 9、resize 10、insert 迭代器失效問題 11、erase 12、帶參初始化 13、迭代器初始化 14、析構函數 完整版代碼 一、…

一款基于ESP32的迷你四足機器人

一、軟件介紹 增加自定義動作模式&#xff0c;可以在小程序中自定義一個最多10個步驟的動作。 附件中&#xff1a;帶自定模式固件bin.zip esp32c3固件文件 燒錄下圖設置 無串口版本esp32c3開發板燒錄前先按住BOOT鍵再插線進入燒錄模式&#xff0c;LoadMode選擇USB。 二、AP…

2023團體程序設計天梯賽——模擬賽和總決賽題

M-L1-1 嫑廢話上代碼 Linux 之父 Linus Torvalds 的名言是&#xff1a;“Talk is cheap. Show me the code.”&#xff08;嫑廢話&#xff0c;上代碼&#xff09;。本題就請你直接在屏幕上輸出這句話。 輸入格式&#xff1a; 本題沒有輸入。 輸出格式&#xff1a; 在一行中輸出…

java resource ‘process/qingjia.png‘ not found

resource中的資源在target中沒有&#xff0c;導致報錯&#xff0c;如下圖所示&#xff1a; 解決辦法&#xff1a;在pom文件中添加如下代碼&#xff1a; 重新執行代碼&#xff0c;就能在target中看到png文件了。 類似的錯誤參考鏈接&#xff1a;mybatis-plus框架報錯&#x…

STL模板參數類字段名稱類型參數模板解析方法

指向成員的指針允許您引用類對象的非靜態成員。不能使用指向成員的指針指向靜態類成員&#xff0c;因為靜態成員的地址不與任何特定對象相關聯。若要指向靜態類成員&#xff0c;必須使用普通指針。可以使用指向成員函數的指針&#xff0c;其方式與指向函數的指針相同。您可以比…

【C/C++】可變參數va_list與格式化輸出

va_list與格式化輸出 va_list 文章目錄 va_list與格式化輸出va_list格式化輸出snprintfvsnprintfvasprintf 實例 va_list是在C語言中解決變參問題的一組宏&#xff0c;變參問題是指參數的個數不定&#xff0c;可以是傳入一個參數也可以是多個 用法&#xff1a;在函數里定義va_…

Java 手寫設計HashMap源碼,讓面試官膜拜

Java 手寫HashMap源碼&#xff0c;讓面試官膜拜 一&#xff0c;手寫源碼 這是一個模仿HashMap的put&#xff0c;get功能的自定義的MyHashMap package cn.wxs.demo;import java.io.Serializable; import java.util.*; import java.util.function.BiConsumer;class MyHashMap&…

面向對象三大特征——封裝

目錄 1. 封裝概述&#xff08;封裝與隱藏&#xff09; 2. private關鍵字 3. Getter & Setter方法 4. 變量訪問原則和this關鍵字 5. 構造方法 5.1 構造方法概述 5.2 構造方法和set方法的比較 6. 靜態 6.1 靜態概述 6.2 靜態效果 6.3 靜態變量和非靜態變量的區別 …