C69-贪心综合
原题链接：28705.NoteSC++
2025-08-24 12:10:38
发布于：江苏
4阅读
0回复
0点赞
一、洒水问题
将面积转换为直线的问题，勾股定理。
#include <bits/stdc++.h>
using namespace std;
void f(){
int n, ans = 0;
double r[6000] = {}, L = 20;
cin >> n;
for(int i=1; i<=n; i++){
cin >> r[i];
}
sort(r+1, r+1+n, greater<double>() );//半径从大到小排序
for (int i=1; i<=n; i++){
double s = sqrt(r[i]*r[i] - 1);
L -= 2*s;
ans ++;
if (L <= 0){
break;
}
}
cout << ans << endl;
}
int main(){
int T;
cin >> T;
while (T--){
f();
}
return 0;
}
二、排队接水2
n个水龙头问题，策略一样，分成m队处理前缀和即可。
#include <bits/stdc++.h>
using namespace std;
int a[1005], n, m, ans;
int b[1005]; //临时组队
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++) cin>>a[i];
sort(a+1, a+1+n);
//n个人分成m个队伍
for (int i=0; i<m; i++){
int k = 1;
for (int j=1; j<=n; j++){
if (j%m == i){
b[k++] = a[j];
}
}
//计算当前这个队伍的等待时间
for (int j=1; j<k; j++) b[j] += b[j-1], ans += b[j];
}
cout << ans;
return 0;
}
这里空空如也
有帮助，赞一个