d900 - NOIP2010 2.接水问题
題目描述
學校有m個水龍頭，n個學生需要接水，每個學生需要接水量wi。學生按照順序接水，當一個學生接完水後，下一個學生立即接替他的位置。求所有學生都接完水需要的總時間。
解題思路
本題可以使用貪心策略。每次找到剩餘水量最少的m個學生，讓他們同時接水，接水量為剩餘水量中的最小值。然後更新每個學生的剩餘水量，如果某個學生的剩餘水量為0，則用下一個學生的接水量替換。重複這個過程直到所有學生都接完水。最後，需要加上剩餘學生中最大剩餘水量。
複雜度分析
- 時間複雜度: O(n*m)
- 空間複雜度: O(m)
程式碼
#include <iostream>
using namespace std;
int ans,a[101],n,m,w[10001],it;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
it=m;
for(int i=0;i<n;++i){
cin >> w[i];
if(i<it){
a[i]=w[i];
}
}
while(it<=n){
int tmp=101;
for(int i=0;i<m;++i){
tmp=min(tmp,a[i]);
}
ans+=tmp;
for(int i=0;i<m;++i){
a[i]-=tmp;
if(a[i]==0){
if(it<n)a[i]=w[it];
++it;
}
}
}
int tmp=0;
for(int i=0;i<m;++i){
tmp=max(a[i],tmp);
}
cout << ans+tmp;
}