C68-排队接水问题
原题链接：28705.NoteSC++
2025-08-23 12:13:36
发布于：江苏
9阅读
0回复
0点赞
一、最简单的排队接水问题
接水最快的人先接
#include<bits/stdc++.h>
using namespace std;
int n, a[1005], sum;
int main(){
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
sort(a+1, a+1+n);
for(int i=1; i<=n; i++){
sum += a[i]*(n-i+1);
}
cout << sum;
return 0;
}
/*
输入：
4
2 6 4 5
输出：
36
*/
二、升级一点的接水问题
#include<bits/stdc++.h>
using namespace std;
struct node{
int time;
int idx;
}a[1005];
int n, sum;
bool cmp(node x, node y){
return x.time < y.time;
}
int main(){
cin >> n;
for(int i=1; i<=n; i++) {
cin>>a[i].time;
a[i].idx = i;
}
sort(a+1, a+1+n, cmp);
for (int i=1; i<=n; i++) {
cout<< a[i].idx <<' ';
sum += a[i].time*(n-i);
}
printf("\n%.2lf", sum*1.0/n);
return 0;
}
三、水壶问题
以下是暴力不能通过代码， 需要用前缀和进行优化
#include<iostream>
using namespace std;
int n, a[1005], m;
int main(){
cin >> n;
for (int i=1; i<=n; i++){
cin >> a[i];
}
cin >> m;
while (m--){
int l, r, sum = 0;
cin >> l >> r;
for (int i=l; i<=r; i++) sum+=a[i];
cout<<sum<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个