泉五培训Day4
t1 收果子
题目
【题目描述】
有一个果园，有n棵果树依次排成一排，其中已知第 i 棵果树上结了ai个果子。现在要按照果树编号顺序依次收果子，对于一个能装v个果树的果篮，收果子从第1棵果树开始，如果果篮的剩余容积大于等于当前果树所结的果子，那么就可以将此树上的果子全收下来，否则就要拿一个新的篮子来装果子。特别地，如果果篮容积小于某果树的结果数，那么我们认为这样将永远不能收完果子。
现在假若只能用k个果篮，问按照以上方法能使用不超过k个果篮并收完所有果子的果篮最小容积。
【输入格式】
输入有两行，第一行两个正整数，代表 n、k，意义如题。
第二行 n 个正整数ai，代表每棵果树的结果数。
【输出格式】
输出仅一行，一个正整数，即满足条件的果篮最小容积。
【样例输入】
9 3
1 2 3 4 5 6 7 8 9
【样例输出】
17
【数据规模】
对于 30% 的数据，满足 n, k≦100、ai≦100 。
对于 60% 的数据，满足 n, k≦1000、ai≦105。
对于 80% 的数据，满足 n, k≦10000、ai≦105。
对于 100% 的数据，满足 n, k≦105 、ai≦109。
解析
很显然这是一道二分题，记得加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;
}
t2 食物
题目
【题目描述】
辉夜从月都弄了很多吃的回到了幻想乡，有n种不同的食物，第i种食物的美味度为ti，一份食物的大小为ui，共有vi份。但是麻烦的事情出现了，她要把这些食物运回永远亭，于是辉夜便弄来了m种运载工具。第i种运载工具可以运输大小总和不超过xi的食物，运输一次的费用是yi，总共可以运输zi次。
辉夜打算选取一些食物运回永远亭，他们的美味度之和（每份食物的和，即使他们都是同一种食物）至少是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，ti,ui,vi,xi,yi,zi≤10。
对于100%的数据，1≤n,m≤200，0≤p≤50000，1≤ti,ui,vii,xi,yi,zi≤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;
}
t3 到天堂的路
题目
【题目描述】
到天堂的道路是一个笛卡尔坐标系上一个nxm的长方形通道（顶点在(0,0)和(n,m)），小w从最左边任意一点进入，从右边任意一点走到天堂。
最左最右的距离为n，上下边界距离为m。
其中长方形内有k个star，每个star都有一个整点坐标，star的大小可以忽略不计。
每个star以及长方形上下两个边缘（宇宙的边界）都有引力，所以为了成功到达heaven小w离他们越远越好。
请问小w走到终点的路径上，距离所有星星以及边界的最小距离最大值可以为多少？
【输入格式】
一行三个整数n,m,k。
接下来k行，每行两个整数xi,yi，表示一个点的坐标。
【输出格式】
一行一个整数表示答案，绝对误差不能超过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≤106。
解析
最小距离的最大值，考虑从将几个点，从下界连到上界，这条路径中的最长边的一半，即我们想要的答案。
一条路径的最长边，即最大值。
所有路径中的最长边的最小值，即最小距离。
所以求出最长边的最小值即可。
我们要找到所有路径中的所有最长边（相对于该条路径而言），然后在这些最长边中找到一个最小值，最小值除以二即为答案。
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;
}