@Asuna
2017-02-02T10:47:59.000000Z
字数 4331
阅读 807
题解
题意:给定一个f(x)=6*x^7+8*x^6+7*x^3+5*x^2-y*x,求出它在x属于[0,100]的时候的最小值。
题解:综合题目大意和本次作业的主题。。很容易想到要用三分法求最值(二分法要求单调),于是。。这道题似乎就是一个裸的三分了。。。。(注意要保留4位小数而题目中没说哦~)
参考代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int t;
double y,mid,mmid,l,r;
double getf(double x,double y)
{
return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
}
int main()
{
cin>>t;
while(t--)
{
cin>>y;
l=0;
r=100;
for (int i=0; i<200; i++)
{
mid=(l+r)/2;
mmid=(mid+r)/2;
if (getf(mid,y)<getf(mmid,y)) r=mmid;
else l=mid;
}
printf("%.4lf\n",getf(mid,y));
}
return 0;
}
题意:给定三个数列,长度分别为l,m,n,都属于0~500。现在要任意组合这三个数列中的数看相加能否为x,能输出yes,不能输出no,有1000个询问。
题解:一开始想的是直接三个数列依次相加,但是这样是500*500*500*1000,不用想肯定会爆炸。再加上这次的主题是二分,于是想到了一个算法:把一个数列拿去排序然后二分看能否等于x,但在t了几发之后发现好像500*500*log500*1000也会爆炸。。。然后想了一会儿发现自己傻逼了,既然可以一个拿来二分,那就可以预处理出三个数组中两个数组的和的值,放在一个新的数组里面然后就可以优化成500*log(500*500)*1000,这样就不会爆炸了(智商受限严重)。。。
参考代码:
#include<iostream>
#include<algorithm>
using namespace std;
int l,m,n,d=1,t,k;
long long x;
bool bo1,bo2;
int main()
{
ios::sync_with_stdio(false);
while(cin>>l>>m>>n)
{
long long a[505],b[505],c[505],p[250005];
k=1;
for(int i=1; i<=l; i++)
cin>>a[i];
for(int i=1; i<=m; i++)
cin>>b[i];
for(int i=1; i<=n; i++)
cin>>c[i];
for(int i=1; i<=l; i++)
for(int j=1; j<=m; j++)
{
p[k]=a[i]+b[j];
//cout<<p[k]<<" ";
k++;
//cout<<p[k]<<" ";
}
//cout<<endl;
sort(p+1,p+k);
//for (int i=1; i<=k-1; i++)
// cout<<p[k]<<" ";
cin>>t;
cout<<"Case "<<d++<<":"<<endl;
while(t--)
{
cin>>x;
bo1=false;
bo2=false;
for (int i=1; i<=n; i++)
{
int l=1,r=k-1;
while (l<=r)
{
int mid=(l+r)/2;
if (p[mid]+c[i]==x)
{
bo1=true;
bo2=true;
break;
}
else if (p[mid]+c[i]<x)
{
l=mid+1;
}
else r=mid-1;
}
if (bo1) break;
}
if (bo1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return 0;
}
题意:已知农夫在n天中每天的花费,要求把这n天分作m组,每组的天数必然是连续的,要求分得各组的花费之和应该尽可能地小,最后输出各组花费之和中的最大值。
题解:二分答案,可知最小的可能就是a[i]中的最大值,而最大的可能是整个a数组的和,于是取到了l和r,二分答案检查是否满足刚好可以分为m组,如果大于m组说明偏小了,可以增大,反之可以减小。
参考代码:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,sum,t,a[100005],ans,l,r,mid;
bool judge(int ans)
{
sum=0;
t=1;
for (int i=1; i<=n; i++)
{
if (sum+a[i]<=ans) sum+=a[i];
else
{
sum=a[i];
t++;
}
}
if (t>m) return 0;
else return 1;
}
int main()
{
cin>>n>>m;
for (int i=1; i<=n; i++)
{
cin>>a[i];
l=max(l,a[i]);
r+=a[i];
}
while (l<=r)
{
mid=(l+r)/2;
if (judge(mid)) r=mid-1;
else l=mid+1;
}
cout<<mid<<endl;
return 0;
}
题意:有一条河长L,中间N块石头,最多去掉M块,求任意两个石头间最小距离的最大值.
题解:二分最小值,再比较最小值是mid时去掉的石头个数来改动l和r,题目的思路和C类似。值得注意的是有可能把所有石子全部取完。。所以在二分的初始时候要把r设置的大一些(wa了两发。。。)
参考代码:
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int l,n,m,a[50005],t,k,l1,r,mid;
bool judge(int mid)
{
t=0;
k=0;
int i=1;
while (i<=n+1)
{
if (a[i]-a[k]>=mid)
{
i++;
k=i-1;
}
else
{
i++;
t++;
}
}
if (t<=m) return 1;
else return 0;
}
int main()
{
cin>>l>>n>>m;
a[0]=0;
a[n+1]=l;
for (int i=1; i<=n; i++)
cin>>a[i];
sort(a,a+n+1);
l1=0;
r=l+l;
while (r-l1>1)
{
mid=(r+l1)/2;
if (judge(mid)) l1=mid;
else r=mid;
}
cout<<l1<<endl;
return 0;
}
题意:有n种设备,而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产,而每个厂家生产的同种设备都会存在两个方面的差别:B和P。每种设备都各需要1个,考虑到性价比问题,要求所挑选出来的n件设备,要使得B/P最大。其中B为这n件设备的带宽的最小值,P为这n件设备的总价。
题解:额。。看了下数据范围。。发现好像只要枚举所有可能符合条件的B值也可以。。。就没有用二分来做。。。
参考代码:
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
struct note
{
int b,p;
}a[105][105];
int n,num[105],maxx[105],minn[105],t,sum,s1,s2,mp;
double ans;
int find(int b)
{
sum=0;
for(int i=1; i<=n; i++)
{
mp=1000000000;
for(int j=1; j<=num[i]; j++)
{
if (a[i][j].b>=b)
mp=min(mp,a[i][j].p);
}
sum+=mp;
}
return sum;
}
int main()
{
cin>>t;
while(t--)
{
ans=0;
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>num[i];
for(int j=1; j<=num[i]; j++)
cin>>a[i][j].b>>a[i][j].p;
}
for(int i=1; i<=n; i++)
{
minn[i]=a[i][1].b;
maxx[i]=a[i][1].b;
for (int j=2; j<=num[i]; j++)
{
maxx[i]=max(maxx[i],a[i][j].b);
minn[i]=min(minn[i],a[i][j].b);
}
}
s1=minn[1];
s2=maxx[1];
for(int i=2; i<=n; i++)
{
s1=min(s1,minn[i]);
s2=min(s2,maxx[i]);
}
for(int i=s1; i<=s2; i++)
ans=max(ans,(double)i/(double)find(i));
printf("%.3lf\n",ans);
}
return 0;
}
题意:求人从左向右走动时,影子的长度L的最大值。
题解:感觉是一道数学题。。因为明显从灯下开始往右走影子先会慢慢变长,但是到了某一点影子开始投射在墙上,于是又会慢慢变短。因此这个函数是一个先增后减的函数,满足三分法。。然后推出L和人到灯的水平距离x满足函数式L=D-x+H-D*(H-h)/x。然后x的初始值可以由相似三角形得到h/H=(D-x)/D => x=D-D*h/H,x最大值为D,即确定了l一开始为D-D*h/H,r一开始为D。
参考代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double D,H,h,l,r,mid,mmid;
int t;
double getf(double x)
{
return D-x+H-D*(H-h)/x;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>H>>h>>D;
l=(H-h)*D/H;
r=D;
while (l<r-0.0000000001)
{
mid=(l+r)/2;
mmid=(mid+r)/2;
if (getf(mid)>=getf(mmid)) r=mmid;
else l=mid;
}
printf("%.3lf\n",getf(mid));
}
return 0;
}