程序设计与算法 | (20) Lecture(10) OJ作业

OJ地址

Lecture (10)包含以下三道编程题，可以在上面的OJ提交。

059:派

#include <iostream>
#include <algorithm>
#include <iomanip> //setprecision需要此头文件
#include <cmath>
using namespace std;#define PI acos(-1.0)
#define eps 1e-6
#define N 10000
int r[N+10];
int n,f;
bool Valid(double V)
{
    int total = 0;for(int i = 0;i < n; ++i) {
    double n1 =  r[i]*r[i] / V;total += n1;if( total >= f)return true;}return false;
}
int main()
{
    cin >> n >> f;++f;double maxV = 0;for(int i = 0;i < n; ++i) {
    cin >> r[i];maxV = max(maxV,(double)r[i]*r[i]);}double L = 1e-4,R = maxV;while( R - L > eps ) {
    double midV = L + (R-L )/2;if( Valid(midV) )L = midV;elseR = midV;}cout << fixed << setprecision(3) << PI * L<<endl;return 0;
}

060:月度开销

#include <iostream>
using namespace std;
#define N 100000
int a[N+10];int Count(int a[],int size,int mid)
{
    int sum1 = 0;int count = 1;for(int i=0;i<size;i++){
    sum1+=a[i];if(sum1>mid){
    sum1 = a[i];count++;}}return count;
}int main(int argc, const char * argv[]) {
    int n,m;cin>>n>>m;int sum = 0;int maxN = -1;for(int i=0;i<n;i++){
    cin>>a[i];if(a[i]>maxN)maxN=a[i];sum += a[i];}int L=maxN,R=sum;int mid;int count;int lastMid;while(L<=R){
    mid = L+(R-L)/2;count = Count(a,n,mid);if(count<=m){
    R=mid-1;lastMid = mid;}elseL=mid+1;}cout<<lastMid<<endl;return 0;
}

061:Aggressive cows

#include <iostream>
#include <algorithm>
using namespace std;
#define N 100000
int a[N+10];int Count(int a[],int size,int mid)
{
    int count=1;int pos = a[0];for(int i=1;i<size;i++){
    if(a[i]>=pos+mid){
    count++;pos = a[i];}}return count;
}
int main(int argc, const char * argv[]) {
    int n,c;cin>>n>>c;for(int i=0;i<n;i++){
    cin>>a[i];}sort(a,a+n);int L=1,R=a[n-1]/c;int mid;int count;int lastMid;while(L<=R){
    mid = L + (R-L)/2;count = Count(a,n,mid);if(count>=c){
    L=mid+1;lastMid = mid;}elseR=mid-1;}cout<<lastMid<<endl;return 0;
}