T1 收果子
题目
【题目描述】
有一个果园，有n棵果树依次排成一排，其中已知第 i 棵果树上结了a个果子。现在要按照果树编号顺序依次收果子，对于一个能装v个果树的果篮，收果子从第1棵果树开始，如果果篮的剩余容积大于等于当前果树所结的果子，那么就可以将此树上的果子全收下来，否则就要拿一个新的篮子来装果子。特别地，如果果篮容积小于某果树的结果数，那么我们认为这样将永远不能收完果子。
现在假若只能用k个果篮，问按照以上方法能使用不超过k个果篮并收完所有果子的果篮最小容积。
【输入格式】
输入有两行，第一行两个正整数，代表 n、k，意义如题。
第二行 n 个正整数a，代表每棵果树的结果数。
【输出格式】
输出仅一行，一个正整数，即满足条件的果篮最小容积。
【样例输入】
9 3
1 2 3 4 5 6 7 8 9
【样例输出】
17
【数据规模】
对于 30% 的数据，满足 n, k≦100、a≦100 。
对于 60% 的数据，满足 n, k≦1000、a≦10。
对于 80% 的数据，满足 n, k≦10000、a≦10。
对于 100% 的数据，满足 n, k≦10 、a≦10。
解析
很显然这是一道二分题，记得加long long 就行了。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
const int N=1e5+;
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 ;
int cnt=,water=v;
for(int i=;i<=n;i++)
{
if(a[i]<=water) water-=a[i];
else if(a[i]>water)
{
cnt++;
water=v-a[i];
}
}
if(cnt<=k) return ;
return ;
}
signed main()
{
int l=,r=,mid;
cin>>n>>k;
for(int i=;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)/;
if(check(mid))
{
r=mid-;
ans=mid;
}
else l=mid+;
}
cout<<ans;
return ;
}
T2 食物
题目
【题目描述】
辉夜从月都弄了很多吃的回到了幻想乡，有n种不同的食物，第i种食物的美味度为t，一份食物的大小为u，共有v份。但是麻烦的事情出现了，她要把这些食物运回永远亭，于是辉夜便弄来了m种运载工具。第i种运载工具可以运输大小总和不超过x的食物，运输一次的费用是y，总共可以运输z次。
辉夜打算选取一些食物运回永远亭，他们的美味度之和（每份食物的和，即使他们都是同一种食物）至少是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,u,v,x,y,z≤10。
对于100%的数据，1≤n,m≤200，0≤p≤50000，1≤t,u,vi,x,y,z≤100。
解析
我们把问题拆成两部分：
1、选出美味度和不小于p的食物并且空间最小。
2、选出空间之和不小于第一步的结果并且费用尽可能的少。
第一部分只需用背包即可解决。
第二部分我们不妨将状态和答案互换，以费用为状态，以空间为答案，因为答案不超过50000，所以这样是可行的。
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=;
const int M=;
int n,m,p;
int q,sum,ans;
int t[N],u[N],v[N];
int f[M],W[N*],V[N*];
int read() //快读
{
int num=;char ch=getchar();
while(ch<'' || ch>'') ch=getchar();
while(ch>='' && ch<='') num=(num<<)+(num<<)+ch-'',ch=getchar();
return num;
}
int main()
{
int T=read();
while(T--)
{
//求出最小空间
sum=;
memset(V,,sizeof(V));
memset(W,,sizeof(W));
memset(f,,sizeof(f));
n=read();m=read();p=read();
for(register int i=;i<=n;i++)
{
t[i]=read();u[i]=read();v[i]=read();
int j;
for(j=;j<=v[i];j<<=)
{
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=;i<=sum;i++)
for(register int j=M-;j>=W[i];j--) f[j]=max(f[j],f[j-W[i]]+V[i]);
q=-;
for(register int i=;i<M;i++) if(f[i]>=p){q=i;break;}//求出满足美味度不小于p的最小价值
if(q<)//不成立的情况
{
cout<<"TAT"<<endl;
for(register int i=;i<=m;i++) q=read(),q=read(),q=read();
continue;
}
//求出尽可能小的费用
memset(V,,sizeof(V));
memset(W,,sizeof(W));
memset(f,,sizeof(f));
sum=;
for(register int i=;i<=m;i++)
{
t[i]=read();u[i]=read();v[i]=read();
int j;
//二进制拆分
for(register int j=;j<=v[i];j<<=)
{
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=;i<=sum;i++)
for(register int j=;j>=W[i];j--) f[j]=max(f[j],f[j-W[i]]+V[i]);
ans=-;
for(register int i=;i<=;i++) if(f[i]>=q){ans=i;break;}//求出最小花费
if(ans<){cout<<"TAT"<<endl;continue;}
cout<<ans<<endl;
}
return ;
}
T3 到天堂的路
题目
【题目描述】
到天堂的道路是一个笛卡尔坐标系上一个nxm的长方形通道（顶点在(0,0)和(n,m)），小w从最左边任意一点进入，从右边任意一点走到天堂。
最左最右的距离为n，上下边界距离为m。
其中长方形内有k个Star，每个Star都有一个整点坐标，Star的大小可以忽略不计。
每个Star以及长方形上下两个边缘（宇宙的边界）都有引力，所以为了成功到达heaven小w离他们越远越好。
请问小w走到终点的路径上，距离所有星星以及边界的最小距离最大值可以为多少？
【输入格式】
一行三个整数n,m,k。
接下来k行，每行两个整数x,y，表示一个点的坐标。
【输出格式】
一行一个整数表示答案，绝对误差不能超过10。
【输入样例】
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=+;
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=;i<=k;i++) cin>>x[i]>>y[i];
for(int i=;i<=k;i++) dis[i]=m-y[i];
dis[k+]=m;
dis[]=2e9;
while()
{
int mi=;
for(int i=;i<=k+;i++)
if(!water[i] && dis[i]<dis[mi]) mi=i;
ans=max(ans,dis[mi]);
if(mi==k+)
{
cout<<ans/;
return ;
}
for(int i=;i<=k;i++) dis[i]=min(dis[i],calc(x[i],y[i],x[mi],y[mi]));
dis[k+]=min(dis[k+],y[mi]);
water[mi]=;
}
return ;
}