概述
001:派
总时间限制: 1000ms 内存限制: 65536kB
描述
我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。
我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。
输入
第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。
第二行包含N个1到10000之间的整数，表示每个派的半径。
输出
输出每个人能得到的最大的派的体积，精确到小数点后三位。
样例输入
3 3
4 3 3
样例输出
25.133
https://blog.csdn.net/hey_dom2016/article/details/81486081
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double pi=acos(-1.0);
int n,f;
double r[10010];
bool check(double d){
int cnt=0;
for(int i=0;i<n;i++){
int tmp=floor(r[i]/d);
cnt+=tmp;
}
if(cnt>=f+1) return true;
else return false;
}
int main(){
cin>>n>>f;
for(int i=0;i<n;i++){
int tmp;
cin>>tmp;
r[i]=tmp*tmp*pi;
}
sort(r,r+n);
double l=1,h=r[n-1];
double s=-1;
while(h-l>1e-5){
double mid=l+(h-l)/2;
if(check(mid))
l=mid;
else
h=mid;
}
printf("%.3lf n",l);
return 0;
}
002:月度开销总时间限制: 1000ms 内存限制: 65536kB
描述
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
输入
第一行包含两个整数N,M，用单个空格隔开。
接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。
输出
一个整数，即最大月度开销的最小值。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
提示
若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。
https://blog.csdn.net/abc15766228491/article/details/78827946
#include<iostream>
#include<cstdio>
#define MAX 100010
using namespace std;
bool judge(int mid, int a[], int n, int m)
{
int i,sum=0,t=0;
for(i=0;i<n;i++)
{
if(sum+a[i]>mid) //如果前几个月加上这个月的钱大于这次尝试的fajo月开销，那么说明这个月的钱应该放在下个fajo月里
{
sum=a[i];
t++; //找到一个fajo月
}
else sum+=a[i]; // 否则就加上这个月
}
//如果按照mid的分割方法，最大分割出t个月大于m，则可以继续增加开销，
// 注意，这里是说，最少分出的月份是t，那么t>=m，则可以继续增加开销，以便使t变小
if(t>=m) return true;
else return false;
}
int main()
{
int total=0, max=0, a[MAX], n, m, i;
cin>>n>>m;
for(i=0;i<n;i++)
{
cin>>a[i];
total+=a[i]; //记录开销的总和
if(max<a[i]) max=a[i]; //记录开销的最大值
}
int l=max, r=total, mid;
while(l<=r)
{
mid=(l+r)/2;
if(judge(mid,a,n,m)) l=mid+1; //如果可以按照要求分，就说明fajo月的开销可以变大一点
else r=mid-1; // 如果不可以，则说明fajo月开销应该变小
}
cout<<mid<<endl;
return 0;
}
003:Aggressive cows
总时间限制: 1000ms 内存限制: 65536kB
描述
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
输入
-
Line 1: Two space-separated integers: N and C
-
Lines 2…N+1: Line i+1 contains an integer stall location, xi
输出 -
Line 1: One integer: the largest minimum distance
样例输入
5 3
1
2
8
4
9
样例输出
3
提示
OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended.
来源
USACO 2005 February Gold
https://blog.csdn.net/qq_41233726/article/details/78825197
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,c;
int a[1000005];
bool ok(int x) //判断函数
{
int i,res,la;
res=1; la=0; i=1;
while(i<n)
{
while(a[i]-a[la]<x) i++;
if(i<n) res++; //是否出界的判断！
if(res>=c) return true;
la=i;
i++;
}
return false;
}
int main()
{
int i,l,r,mid,ans=0;
scanf("%d%d",&n,&c);
for(i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n); //排序
l=0; r=1000000000;
while(l<=r)
{
mid=(l+r)/2;
if(ok(mid))
{
ans=mid; l=mid+1;
}
else r=mid-1;
}
printf("%dn",ans);
return 0;
}
最后
以上就是干净可乐为你收集整理的程序设计与算法（一）第11周测验(2019夏季)的全部内容，希望文章能够帮你解决程序设计与算法（一）第11周测验(2019夏季)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![P3138 [USACO16FEB]负载平衡Load Balancing_Silver](/uploads/reation/bcimg2.png)
发表评论 取消回复