洛谷P1223 排隊接水

来源:https://www.cnblogs.com/Tomorrowland/p/18343729
-Advertisement-
Play Games

P1223 排隊接水 題目描述 有 \(n\) 個人在一個水龍頭前排隊接水,假如每個人接水的時間為 \(T_i\),請編程找出這 \(n\) 個人排隊的一種順序,使得 \(n\) 個人的平均等待時間最小。 輸入格式 第一行為一個整數 \(n\)。 第二行 \(n\) 個整數,第 \(i\) 個整數 ...


P1223 排隊接水

題目描述

\(n\) 個人在一個水龍頭前排隊接水,假如每個人接水的時間為 \(T_i\),請編程找出這 \(n\) 個人排隊的一種順序,使得 \(n\) 個人的平均等待時間最小。

輸入格式

第一行為一個整數 \(n\)

第二行 \(n\) 個整數,第 \(i\) 個整數 \(T_i\) 表示第 \(i\) 個人的接水時間 \(T_i\)

輸出格式

輸出文件有兩行,第一行為一種平均時間最短的排隊順序;第二行為這種排列方案下的平均等待時間(輸出結果精確到小數點後兩位)。

樣例 #1

樣例輸入 #1

10 
56 12 1 99 1000 234 33 55 99 812

樣例輸出 #1

3 2 7 8 1 4 9 6 10 5
291.90

提示

\(1\le n \leq 1000\)\(1\le t_i \leq 10^6\),不保證 \(t_i\) 不重覆。

思路:

  • 我們可以採取貪心的策略,將接水時間慢的人放在後面排隊,那麼後面的人的排隊時間就較短,這是我們的直覺告訴我們的結果,並且,這也是貪心策略的局部最優解,我們只需要儘可能的將接水時間長的人排在後面接水,那麼其他人等待的時間就會減少,到最終時,總的接水時間就會最少。
  • 那麼我們這種的接水策略是否能嚴格的數學證明呢?其實大部分的時候,我們貪心策略的思想,就是非常正常的常識,只要我們舉不出明顯的反例來證明我們的策略不可行,我們就可以使用貪心策略,不過這題我們還真的可以來進行嚴格的數學證明我們這個策略的可行性。

證明策略的可行性

  • 從這裡也可以看出,貪心策略往往與排序是一起出現的,每次枚舉最優的解法,最終達到最優的結果!

代碼:

#include<algorithm>
#include<iostream>
using namespace std;
struct people {
	int t;
	int id;
}a[1005];
//按接水時間來升序排列
bool compare(people& a, people& b) {
	return a.t < b.t;
}
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].t;
		a[i].id = i;
	}
	sort(a + 1, a + 1 + n, compare);
	for (int i = 1; i <= n; i++) {
		cout << a[i].id << " ";
	}
	cout << endl;
	double sum = 0;
    //這裡為什麼要✖(n-i)呢,因為第一個人洗澡的時候,後面n-1個人都要等它,第二個人,後面的n-2個人又要等他
	for (int i = 1; i <= n - 1; i++) sum += a[i].t*(n-i);
	double average = sum / n;
	printf("%.2lf", average);
	return 0;
}

部分代碼的解釋:

計算sum的部分涉及到如下的代碼段:

double sum = 0;
for (int i = 1; i <= n - 1; i++)
    sum += a[i].t * (n - i);

這段代碼的目的是計算加權平均數的值,其具體含義是在對人員按照t屬性排序後,計算每個人在隊列中的等待時間乘以其後面人數的總和。讓我們分析一下為什麼要乘以(n - i)

  1. 排序的影響

    • 數組 a[] 中的人員按照 t 屬性從小到大排序。
    • 排序後,a[i].t 表示第 i 個人的處理時間。
  2. 等待時間的計算

    • 在排序後的順序中,如果第 i 個人在隊列中,那麼他前面有 i - 1 個人,因此他的等待時間就是前面所有人的處理時間之和。
  3. 加權求和的原理

    • 對於第 i 個人,他的等待時間為 a[i].t * (n - i)。這裡 (n - i) 表示的是他後面的人數,因為他後面的每個人都要等待他的處理時間。
  4. 計算總和

    • sum += a[i].t * (n - i) 就是把每個人的等待時間乘以後面的人數加起來,得到總的加權等待時間之和。
  5. 最終的平均值

    • average = sum / n 就是將這個加權等待時間之和除以總人數 n,得到的是每個人的平均等待時間。

因此,乘以 (n - i) 的操作是為了正確地計算每個人的等待時間對整體加權平均數的貢獻,確保了按照題目要求正確計算平均值。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 前言 Gunicorn是一種流行的WSGI HTTP伺服器,常用於部署Django和Flask等Python Web框架程式。Gunicorn具有輕量級、高穩定性和高性能等特性,可以輕易提高Python WSGI App運行時的性能。 基本原理 Gunicorn採用了pre-fork模型,也就是一個 ...
  • 記憶體拷貝 - memcpy 描述 C 庫函數 void *memcpy(void *str1, const void *str2, size_t n) 從存儲區 str2 複製 n 個位元組到存儲區 str1。 memcpy 是最快的記憶體到記憶體複製子程式。 它通常比必須掃描其所複製數據的strcpy ...
  • playwright也是可以做介面測試的,但個人覺得還是沒有requests庫強大,但和selenium相比的話,略勝一籌,畢竟支持API登錄,也就是說可以不用交互直接調用介面操作了。 怎麼用 既然是API的測試了,那肯定就別搞UI自動化那套,搞什麼瀏覽器交互,那叫啥API測試,純屬扯淡。 也不像有 ...
  • 題目要求 給你一個由 n 個整數組成的數組 nums ,和一個目標值 target 。請你找出並返回滿足下述全部條件且不重覆的四元組 [nums[a], nums[b], nums[c], nums[d]] (若兩個四元組元素一一對應,則認為兩個四元組重覆): 0 <= a, b, c, d < n ...
  • 2018年6月,大三暑假 那一天,我投遞了家裡附近的一家公司有響應了,他線上問我什麼時候可以去面試,我說什麼時候都行。 HR:“要不你下午來吧?” 我:“行,我家裡離面試地點不遠” 我去面試之前,現在都會提前看看這家公司是做什麼業務的,先瞭解下。 因為在之前的面試已經吃過類似的虧了,HR問我為什麼要 ...
  • PART 1: while迴圈 雙重for迴圈 1. 迴圈結構(while迴圈語句) 基本格式 while(判斷條件語句) { 迴圈體語句; } 擴展格式 初始化語句; while(判斷條件語句) { 迴圈體語句; 控制條件語句; } 2. 迴圈結構(for迴圈和while迴圈的區別) for迴圈和 ...
  • 寫在前面 前面給了關於java方法和數組的十題編程題,如果你能有思路很快速地完成它,說明你這部分的基礎知識很好,接下來就來看看後面的面向對象的相關知識吧! 面向對象 概述:不斷地創建對象,使用對象,指揮對象做事情的思想。 類和對象的關係: 類: 是java的基本單位,主要使用用於描述現實生活的事物。 ...
  • # 字元串長度 - strlen() 描述 C 庫函數 size_t strlen(const char *str) 計算字元串 str 的長度,直到空結束字元,但不包括空結束字元。 聲明 下麵是 strlen() 函數的聲明。 size_t strlen(const char *str) 參數 s ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...