泉五培训Day4

t1 收果子

题目

【题目描述】

    有一个果园，有n棵果树依次排成一排，其中已知第 i 棵果树上结了a_i个果子。现在要按照果树编号顺序依次收果子，对于一个能装v个果树的果篮，收果子从第1棵果树开始，如果果篮的剩余容积大于等于当前果树所结的果子，那么就可以将此树上的果子全收下来，否则就要拿一个新的篮子来装果子。特别地，如果果篮容积小于某果树的结果数，那么我们认为这样将永远不能收完果子。

    现在假若只能用k个果篮，问按照以上方法能使用不超过k个果篮并收完所有果子的果篮最小容积。

【输入格式】

    输入有两行，第一行两个正整数，代表 n、k，意义如题。

    第二行 n 个正整数a_i，代表每棵果树的结果数。

【输出格式】

     输出仅一行，一个正整数，即满足条件的果篮最小容积。

【样例输入】

9 3

1 2 3 4 5 6 7 8 9

【样例输出】

17

【数据规模】

对于 30% 的数据，满足 n, k≦100、a_i≦100 。

对于 60% 的数据，满足 n, k≦1000、a_i≦10⁵。

对于 80% 的数据，满足 n, k≦10000、a_i≦10⁵。

对于 100% 的数据，满足 n, k≦10⁵ 、a_i≦10⁹。

解析

很显然这是一道二分题，记得加long long 就行了。

code

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
const int n=1e5+5;
const int inf=0x3f3f3f3f;
int n,k;
int a[n],ans;
int minn=inf;
int maxn=-inf;
bool check(int v)
{
    if(maxn>v||minn>v) return 0;
    int cnt=1,water=v;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=water) water-=a[i];
        else if(a[i]>water)
        {
            cnt++;
            water=v-a[i];
        }
    }
    if(cnt<=k) return 1;
    return 0;
}
signed main()
{
    int l=1,r=0,mid;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        maxn=max(maxn,a[i]);minn=min(minn,a[i]);
        r+=a[i];
    }
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))
        { 
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

view code

 

 

 

 

 

 

t2 食物

题目

【题目描述】

辉夜从月都弄了很多吃的回到了幻想乡，有n种不同的食物，第i种食物的美味度为t_i，一份食物的大小为u_i，共有v_i份。但是麻烦的事情出现了，她要把这些食物运回永远亭，于是辉夜便弄来了m种运载工具。第i种运载工具可以运输大小总和不超过x_i​的食物，运输一次的费用是y_i，总共可以运输z_i次。

辉夜打算选取一些食物运回永远亭，他们的美味度之和（每份食物的和，即使他们都是同一种食物）至少是p。值得注意的是，一份食物可以被拆成几份分批次运输，达到永远亭后再组装起来。但是如果不把一份食物完整的运过去，是无法得到美味度的。辉夜想知道最少需要花费的运输费用是多少。由于辉夜的预算仅有50000，因此如果费用超过这个数或者无法获得p的美味度，输出“tat”。

【输入格式】

第一行一个数test，表示有test组数据。

对于每组数据，第一行有三个整数n，m，p。

接下来n行，每行三个整数t，u，v，描述一种食物。

最后m行，每行三个整数x，y，z，描述一种运载工具。

【输出格式】

 对于每组数据，输出辉夜想知道的答案。注意存在无解的情况。

【输入样例】

4

1 1 7

14 2 1

1 2 2

1 1 10

10 10 1

5 7 2

5 3 34

1 4 1

9 4 2

5 3 3

1 3 3

5 3 2

3 4 5

6 7 5

5 3 8

1 1 1

1 2 1

1 1 1

【样例输出】

4

14

12

tat

【数据规模】

test不会很大。

对于前20%的数据，n,m≤20。

对于前50%的数据，n,m≤30，t_i,u_i​,v_i,x_i,y_i,z_i≤10。

对于100%的数据，1≤n,m≤200，0≤p≤50000，1≤t_i​,u_i,v_ii​,x_i​,y_i,z_i≤100。

解析

我们把问题拆成两部分：

1、选出美味度和不小于p的食物并且空间最小。

2、选出空间之和不小于第一步的结果并且费用尽可能的少。

第一部分只需用背包即可解决。

第二部分我们不妨将状态和答案互换，以费用为状态，以空间为答案，因为答案不超过50000，所以这样是可行的。

code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int n=210;
const int m=50200;
int n,m,p;
int q,sum,ans;
int t[n],u[n],v[n];
int f[m],w[n*7],v[n*7];
int read()    //快读 
{
    int num=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
    return num;
}
int main()
{
    int t=read();
    while(t--)
    {
    //求出最小空间
        sum=0;
        memset(v,0,sizeof(v));
        memset(w,0,sizeof(w));
        memset(f,0,sizeof(f));
        n=read();m=read();p=read();
        for(register int i=1;i<=n;i++)
        {
            t[i]=read();u[i]=read();v[i]=read();
            int j;
            for(j=1;j<=v[i];j<<=1)
            {
                v[++sum]=t[i]*j;
                w[sum]=u[i]*j;
                v[i]-=j;
            }
            if(v[i])
            {
                v[++sum]=t[i]*v[i];
                w[sum]=u[i]*v[i];
            }
        }
        for(register int i=1;i<=sum;i++)
            for(register int j=m-1;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]);
        q=-1;
        for(register int i=1;i<m;i++) if(f[i]>=p){q=i;break;}//求出满足美味度不小于p的最小价值
        if(q<0)//不成立的情况
        {
            cout<<"tat"<<endl;
            for(register int i=1;i<=m;i++) q=read(),q=read(),q=read();
            continue;
        }
        //求出尽可能小的费用
        memset(v,0,sizeof(v));
        memset(w,0,sizeof(w));
        memset(f,0,sizeof(f));
        sum=0;
        for(register int i=1;i<=m;i++)
        {
            t[i]=read();u[i]=read();v[i]=read();
            int j;
            //二进制拆分
            for(register int j=1;j<=v[i];j<<=1)
            {
                v[++sum]=t[i]*j;
                w[sum]=u[i]*j;
                v[i]-=j;
            }
            if(v[i])
            {
                v[++sum]=t[i]*v[i];
                w[sum]=v[i]*u[i];
            }
        }
        for(register int i=1;i<=sum;i++)
            for(register int j=50000;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]);
        ans=-1;
        for(register int i=1;i<=50000;i++) if(f[i]>=q){ans=i;break;}//求出最小花费
        if(ans<0){cout<<"tat"<<endl;continue;} 
        cout<<ans<<endl;
    }
    return 0;
}

view code

 

 

 

 

 

 

t3 到天堂的路

题目

【题目描述】

到天堂的道路是一个笛卡尔坐标系上一个nxm的长方形通道（顶点在(0,0)和(n,m)），小w从最左边任意一点进入，从右边任意一点走到天堂。

最左最右的距离为n，上下边界距离为m。

其中长方形内有k个star，每个star都有一个整点坐标，star的大小可以忽略不计。

每个star以及长方形上下两个边缘（宇宙的边界）都有引力，所以为了成功到达heaven小w离他们越远越好。

请问小w走到终点的路径上，距离所有星星以及边界的最小距离最大值可以为多少？

【输入格式】

 一行三个整数n,m,k。

接下来k行，每行两个整数x_i,y_i，表示一个点的坐标。

【输出格式】

 一行一个整数表示答案，绝对误差不能超过10^-6。

【输入样例】

10 5 2

1 1

2 3

【输出样例】

1.11803399

【数据规模】

对于20%的数据，k≤10。

对于50%的数据，k≤400。

对于80%的数据，k≤1000。

对于100%的数据，k≤6000，n,m≤10⁶。

解析

最小距离的最大值，考虑从将几个点，从下界连到上界，这条路径中的最长边的一半，即我们想要的答案。

一条路径的最长边，即最大值。

所有路径中的最长边的最小值，即最小距离。

所以求出最长边的最小值即可。

我们要找到所有路径中的所有最长边（相对于该条路径而言），然后在这些最长边中找到一个最小值，最小值除以二即为答案。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int n=6000+5;
int water[n];
int n,m,k,x[n],y[n];
double dis[n],ans;
double calc(int x,int y,int l,int r)
{
    return sqrt((double)(x-l)*(x-l)+(double)(y-r)*(y-r));
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=k;i++) dis[i]=m-y[i];
    dis[k+1]=m;
    dis[0]=2e9;
    while(1)
    {
        int mi=0;
        for(int i=1;i<=k+1;i++)
            if(!water[i] && dis[i]<dis[mi]) mi=i;
        ans=max(ans,dis[mi]);
        if(mi==k+1)
        {
            cout<<ans/2;
            return 0;
        }
        for(int i=1;i<=k;i++) dis[i]=min(dis[i],calc(x[i],y[i],x[mi],y[mi]));
        dis[k+1]=min(dis[k+1],y[mi]);
        water[mi]=1;
    }
    return 0;
}

view code