麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 學(xué)院 > 開發(fā)設(shè)計 > 正文

寒假15:算法訓(xùn)練 接水問題

2019-11-14 12:18:34
字體:
供稿:網(wǎng)友

算法訓(xùn)練 接水問題  時間限制:1.0s   內(nèi)存限制:64.0MB      錦囊1模擬即可,要加速可以使用堆優(yōu)化。錦囊2本題的數(shù)據(jù)范圍比較小,可以直接按照題庫模擬,或者也可以使用堆來優(yōu)化算法。問題描述  學(xué)校里有一個水房,水房里一共裝有m 個龍頭可供同學(xué)們打開水,每個龍頭每秒鐘的 供水量相等,均為1。 現(xiàn)在有n 名同學(xué)準(zhǔn)備接水,他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1 到n 編號,i 號同學(xué)的接水量為wi。接水開始時,1 到m 號同學(xué)各占一個水龍頭,并同時打 開水龍頭接水。當(dāng)其中某名同學(xué)j 完成其接水量要求wj 后,下一名排隊等候接水的同學(xué)k 馬上接替j 同學(xué)的位置開始接水。這個換人的過程是瞬間完成的,且沒有任何水的浪費。即 j 同學(xué)第x 秒結(jié)束時完成接水,則k 同學(xué)第x+1 秒立刻開始接水。若當(dāng)前接水人數(shù)n’不足m, 則只有n’個龍頭供水,其它m?n’個龍頭關(guān)閉。 現(xiàn)在給出n 名同學(xué)的接水量,按照上述接水規(guī)則,問所有同學(xué)都接完水需要多少秒。輸入格式  第1 行2 個整數(shù)n 和m,用一個空格隔開,分別表示接水人數(shù)和龍頭個數(shù)。 第2 行n 個整數(shù)w1、w2、……、wn,每兩個整數(shù)之間用一個空格隔開,wi 表示i 號同 學(xué)的接水量。輸出格式  輸出只有一行,1 個整數(shù),表示接水所需的總時間。樣例輸入5 34 4 1 2 1樣例輸出4樣例輸入8 423 71 87 32 70 93 80 76樣例輸出163輸入輸出樣例 1 說明  第1 秒,3 人接水。第1 秒結(jié)束時,1、2、3 號同學(xué)每人的已接水量為1,3 號同學(xué)接完  水,4 號同學(xué)接替3 號同學(xué)開始接水。  第2 秒,3 人接水。第2 秒結(jié)束時,1、2 號同學(xué)每人的已接水量為2,4 號同學(xué)的已接  水量為1。  第3 秒,3 人接水。第3 秒結(jié)束時,1、2 號同學(xué)每人的已接水量為3,4 號同學(xué)的已接  水量為2。4 號同學(xué)接完水,5 號同學(xué)接替4 號同學(xué)開始接水。  第4 秒,3 人接水。第4 秒結(jié)束時,1、2 號同學(xué)每人的已接水量為4,5 號同學(xué)的已接  水量為1。1、2、5 號同學(xué)接完水,即所有人完成接水。  總接水時間為4 秒。數(shù)據(jù)規(guī)模和約定  1 ≤ n ≤ 10000,1 ≤m≤ 100 且m≤ n;  1 ≤ wi ≤ 100。這個題難度中等,不那么難,也不是說一下就出來的。模擬是可以解出來的,有幾個地方可以優(yōu)化下。比如直接求出最小的,然后有一個接口沒人時,只用最大的放完就行了。

代碼,通過了100%的數(shù)據(jù):

import java.util.Scanner;public class 接水問題 {	public static void main(String[] args) {				Scanner sc=new Scanner(System.in);		int n=sc.nextInt();		int m=sc.nextInt();				int[] data=new int[n];		int[] shui=new int[m];				for (int i = 0; i < data.length; i++) {			data[i]=sc.nextInt();			if(i<m)				shui[i]=data[i];		}		int count=0;		while(getBool(shui)){			int min=getMin(shui);			count+=min;			for (int i = 0; i < shui.length; i++) {				shui[i]-=min;				if(shui[i]==0&&m<data.length)					shui[i]=data[m++];			}		}		System.out.PRintln(count);	}	private static int getMin(int[] shui) {		int k=100*100;		for (int i = 0; i < shui.length; i++) {			if(k>shui[i]&&shui[i]>0)				k=shui[i];		}		return k;	}	private static boolean getBool(int[] shui) {		for (int i = 0; i < shui.length; i++) {			if(shui[i]>0)				return true;		}		return false;	}}


發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 日韩2区| 天天草夜夜 | 久久久一区二区三区精品 | 羞羞视频免费网站男男 | 国产精品久久久久久久久久 | 亚州成人在线观看 | 久久久久久久国产视频 | 欧日一级片 | 激情综合网俺也去 | 羞羞视频.www在线观看 | 久久国产一二区 | 日韩精品中文字幕一区二区 | 国产99视频在线观看 | 欧美国产精品一区二区 | 久久久久久久久久久av | 亚洲国产精久久久久久久 | 久久成人午夜视频 | 99影视在线视频免费观看 | 色妞妞视频 | 国产精品久久久久久模特 | av在线免费看网站 | 一级大片一级一大片 | 国产在线观看91一区二区三区 | 性欧美大战久久久久久久免费观看 | 欧美精品黄色 | 日本成人一二三区 | 中国av免费在线观看 | 亚洲综合91 | 爽毛片| 欧美亚洲国产日韩 | 国产午夜精品一区二区三区在线观看 | 国产在线精品区 | 特黄一级小说 | 少妇一级淫片免费看 | 精品1| 天天艹综合 | 最新av网址在线观看 | 欧美在线a | 在线影院av| 久久国产成人精品国产成人亚洲 | 国产资源在线观看视频 |