2018-3-22

1.打水問題

問題描述
　　N個(gè)人要打水，有M個(gè)水龍頭，第i個(gè)人打水所需時(shí)間為Ti，請(qǐng)安排一個(gè)合理的方案使得所有人的等待時(shí)間之和盡量小。
輸入格式
　　第一行兩個(gè)正整數(shù)N M 接下來一行N個(gè)正整數(shù)Ti。
　　N,M<=1000，Ti<=1000
輸出格式
　　最小的等待時(shí)間之和。（不需要輸出具體的安排方案）
樣例輸入
7 3
3 6 1 4 2 5 7
樣例輸出
11

提示
一種最佳打水方案是，將N個(gè)人按照Ti從小到大的順序依次分配到M個(gè)龍頭打水。
例如樣例中，Ti從小到大排序?yàn)?，2，3，4，5，6，7，將他們依次分配到3個(gè)龍頭，則去龍頭一打水的為1，4，7；去龍頭二打水的為2,5；去第三個(gè)龍頭打水的為3,6。
第一個(gè)龍頭打水的人總等待時(shí)間 = 0 + 1 + (1 + 4) = 6
第二個(gè)龍頭打水的人總等待時(shí)間 = 0 + 2 = 2
第三個(gè)龍頭打水的人總等待時(shí)間 = 0 + 3 = 3
所以總的等待時(shí)間 = 6 + 2 + 3 = 11

問題還是比較好理解的，我們先對(duì)大家需要打水的時(shí)間進(jìn)行排序，為了使大家打水的總的時(shí)間最少，我們應(yīng)該使用時(shí)最短的人先打水，那么前m個(gè)人已經(jīng)占用了m個(gè)水龍頭，那么第m+1個(gè)人一定在第1個(gè)水龍頭打水，第m+2個(gè)人一定在第2個(gè)水龍頭打水…第m+m個(gè)人一定在第m個(gè)水龍頭打水。有人可能會(huì)問為什么呢？因?yàn)槲覀兪前凑沼脮r(shí)排序的，那么第一個(gè)一定是先結(jié)束的，那么第m+1個(gè)人自然就過來了，本身第m+1個(gè)人打水的時(shí)間就比較長(zhǎng)，它來的還晚，那么他一定是當(dāng)前所有占水龍頭中打水最慢的那一個(gè)，那么第二個(gè)水龍頭的打完了，第m+2個(gè)人過來了，它也是最慢的那一個(gè)…
1 2 3 4 5 …m
1 2 3 4 5…m
m+1 m+2 m+3…m+m
…
那么第一列的人等待的時(shí)間為t[0]，t[0]+t[m-1]，t[0]+t[m-1]+t[2*m-1]…

#include<iostream> #include<algorithm> using namespace std;const int N = 1000; int t[N+1]; int n,m,s;void cal(){int i,j;for (i=m;i<n;i++){j=i;while (j-m>=0){s+=t[j-m];j-=m;}} }int main(){while (cin>>n>>m){for (int i=0;i<n;i++){cin>>t[i];}if (m==n){cout<<0<<endl;continue;}sort(t,t+n);s=0;cal();cout<<s<<endl;}return 0; }

這個(gè)問題我們只考慮了等待的時(shí)間。

2.排隊(duì)打水問題

問題描述
　　有n個(gè)人排隊(duì)到r個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間t1、t2………..tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們總共花費(fèi)的時(shí)間最少？
輸入格式
　　第一行n，r (n<=500,r<=75)
　　第二行為n個(gè)人打水所用的時(shí)間Ti (Ti<=100)；
輸出格式
　　最少的花費(fèi)時(shí)間
樣例輸入
3 2
1 2 3
樣例輸出

7
數(shù)據(jù)規(guī)模和約定
　　其中80%的數(shù)據(jù)保證n<=10

由于沒有會(huì)員，完全不知道自己寫的對(duì)否。。。
我的理解是，使用的總時(shí)間為等待時(shí)間+排隊(duì)打水的時(shí)間，要使用的總時(shí)間最少，打水的時(shí)間本身就是一個(gè)定值，那么我們只要使等待時(shí)間最短就可以了啊，那么我們只要在上一題的基礎(chǔ)上加上大家打水使用的時(shí)間的總和就可以了？！

#include<iostream> #include<algorithm> using namespace std;const int N = 1000; int t[N+1]; int n,m,s;void cal(){int i,j;for (i=m;i<n;i++){j=i;while (j-m>=0){s+=t[j-m];j-=m;}} }int main(){while (cin>>n>>m){int sum=0;for (int i=0;i<n;i++){cin>>t[i];sum+=t[i]; }sort(t,t+n);s=0;cal();cout<<s+sum<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯-算法提高-打水问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。