对于每个排队的人,找到所有水龙头的最小值
#include<iostream>
using namespace std;
int w[10010];
int q[110];
const int INF = 1e6+10;
int main(){
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d", &w[i]);
q[i] = w[i];
}
for(int i = m + 1; i <= n; i++){
scanf("%d", &w[i]);
int min = INF;
int min_p = 0;
for(int j = 1; j <= m; j++){
if(min > q[j]){
min = q[j];
min_p = j;
}
}
q[min_p] += w[i];
}
int max = 0;
for(int i = 1; i <= m; i++){
if(max < q[i]) max = q[i];
}
printf("%d", max);
return 0;
}
简化写法
#include<iostream>
using namespace std;
int w[10010];
int q[110];
const int INF = 1e6+10;
int main(){
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &w[i]);
}
for(int i = 1; i <= n; i++){
int min_p = 1;
for(int j = 2; j <= m; j++){
if(q[min_p] > q[j]){
min_p = j;
}
}
q[min_p] += w[i];
}
int max = 0;
for(int i = 1; i <= m; i++){
if(max < q[i]) max = q[i];
}
printf("%d", max);
return 0;
}
小根堆写法
#include<cstdio>
#include<queue>
using namespace std;
int main(){
int n, m;
scanf("%d %d", &n, &m);
priority_queue<int, vector<int>, greater<int>> heap;
for(int i = 0; i < m; i++) heap.push(0);
for(int i = 0; i < n; i++){
int w;
scanf("%d", &w);
int min = heap.top();
heap.pop();
heap.push(min + w);
}
for(int i = 0; i < m - 1; i++) heap.pop();
printf("%d", heap.top());
return 0;
}