D,E,F题解

ACM

D - River Hopscotch

题意：

• 有一条河长度为 L，在河的起点和终点分别有2块石头，S到E的距离就是L。河中有n块石头，每块石头到S都有唯一的距离问现在要移除m块石头（S和E除外），每次移除的是与当前最短距离相关联的石头，要求移除m块石头后，使得那时的最短距离尽可能大，输出那个最短距离。

解题思路：

• 和挑战上的二分答案的题有点相像，所以这题也是直接二分距离就行了。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e4+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int a[N];
int n,m;
int check(int x)
{
    int sum=0;
    int k=0;
    for(int i=1;i<=n+1;i++)
    {
        if(a[i]-a[k]<x)
            sum++;//说明可以移除该块
        else
            k=i;
    }
    if(sum>m)
        return 1;
    return 0;
}
int main()
{
    int ll;
    scanf("%d%d%d",&ll,&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    a[n+1]=ll;
    int l=0,r=ll;
    while(l<r)
    {
        int mid=(l+r+1)/2;
        if(check(mid))
            r=mid-1;
        else
            l=mid;
    }
    printf("%d\n",l);
    return 0;
}

E - Communication System

题意：

• 一个公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有$m1$、$m2$、$m3$、...、$mn$个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽和 价格。现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的$n$件设备，要使得$B/P$最大。其中$B$为这$n$件设备的带宽的最小值，$P$为这$n$件设备的总价。

解题思路：

• 首先这道题有很多种解法，但由于在二分三分专题的原因，所以我们必须要向这方面考虑。
• 根据题意我们可以知道，我们要求的其实是$\sum_{k=1} ^{n*m}$B_k $/$ $\sum_{i=1} ^n$ $\sum_{j=1}^{mi.size()}$ min(P_j|B_j>=B_k,P_j,B_j $\in$ mi)，显而易见这个等式肯定不是单调的，所以我们可以用三分来解决（其实就只是加速了一下贪心枚举的过程，这个可以自己思考一下）。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e2+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int n;
int cnt[N];
int b[N][N];
int p[N][N];
int ans[N*N];
double f(int x)
{
    double sum=0;
    for(int i=0;i<n;i++)
    {
        int mi=inf;
        for(int j=0;j<cnt[i];j++)
        {
            if(ans[x]<=b[i][j])
                mi=min(mi,p[i][j]);
        }
        sum+=mi;
    }
    return ans[x]/sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int k=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&cnt[i]);
            for(int j=0;j<cnt[i];j++)
            {
                scanf("%d%d",&b[i][j],&p[i][j]);
                ans[k++]=b[i][j];
            }
        }
        sort(ans,ans+k);
        int l=0,r=k-1;
        int mid,midmid;
        while(l<r-1)
        {
            mid=(l+r)/2;
            midmid=(mid+r)/2;
            if(f(mid)>f(midmid))
                r=midmid;
            else
                l=mid;
        }
        printf("%.3f\n",max(f(r),f(l)));
    }
    return 0;
}

F - Light Bulb

题意：

• 求人落在地上和墙上的影子的最长长度是多少。

解题思路：

• 题目中给的图其实已经看得很清楚，稍微用一下中学的几何知识就可以得出一个$f(x)=(h*D-H*x)/(D-x)+x$的式子$x$是人落在地上的影长，然后根据式子来进行三分就行了。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e4+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
double H,h,D;
double f(double x)
{
    return (h*D-H*x)/(D-x)+x;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf",&H,&h,&D);
        double l=0,r=h/H*D;
        double mid,midmid;
        while(r-l>eps)
        {
            mid=(l+r)/2;
            midmid=(mid+r)/2;
            if(f(mid)<f(midmid))
                l=mid;
            else
                r=midmid;
        }
        printf("%.3f\n",f(l));
    }
    return 0;
}