@sensitive-cs
2017-03-17T17:09:25.000000Z
字数 2523
阅读 811
题解
HDU:2899 STRANGE FUNCTION
题意:
求一个函数在自变量处于0到100闭区间时候的最小值。
思路:
经过求导发现,此函数的二阶导数在定义域内恒大于0,则一阶导数单调递增,又因为在0和100这两个端点一阶导数的值肯定是异号的,所以一阶导数在定义域内有一个零点,原函数在定义域内有一个极小值点也是最小值点。最后就用二分不断逼近此点(一阶导数),达到精度的后几位就ok。
代码:
#include <bits/stdc++.h>
using namespace std;
double y;
double f1x(double t)
{
return (42 * pow(t,6) + 48 * pow(t,5) + 21 * pow(t,2) + 10 * t - y);
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%lf",&y);
double x1 = 0,x2 = 100;
while (fabs(f1x((x1 + x2)/2)) > 1e-8)
{
if (f1x(x1) * f1x((x1 + x2)/2) < 0)
x2 = (x1 + x2)/2;
else
x1 = (x1 + x2)/2;
}
double tmp = (x1 + x2)/2;
double res = 6 * pow(tmp,7) + 8 * pow(tmp,6) + 7 * pow(tmp,3) + 5 * pow(tmp,2) - y * tmp;
printf("%.4f\n",res);
}
return 0;
}
HDU 2141 : CAN YOU FIND IT
题意:
给出三个数组,和一个数X,问是否能在3个数组中分别找到一个数,使得三个数相加等于X。
思路:
二分的一点小变化,即复杂度的改进,先把A,B数组的和存入一个新数组,对于每一个X-Ci,用二分法在新数组中寻找是否存在这样的一个数。
代码:
#include <bits/stdc++.h>
using namespace std;
int a[505];
int b[505];
int c[505];
int ab[255025];
int x[1005];
int myfind(int t,int edge)
{
int left = 0,right = edge - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (ab[mid] == t)
return 1;
else if (ab[mid] > t)
right = mid - 1;
else
left = mid + 1;
}
return 0;
}
int main()
{
int l,n,m,s;
int cnt = 1;
while(scanf("%d%d%d",&l,&n,&m) == 3)
{
int h = 0;
for (int i = 0;i < l;i++)
scanf("%d",&a[i]);
for (int i = 0;i < n;i++)
scanf("%d",&b[i]);
for (int i = 0;i < m;i++)
scanf("%d",&c[i]);
scanf("%d",&s);
for (int i = 0;i < s;i++)
scanf("%d",&x[i]);
sort(a,a+l);
sort(b,b+n);
sort(c,c+m);
printf("Case %d:\n",cnt++);
for (int i = 0;i < l;i++)
for (int j = 0;j < n;j++)
ab[h++] = a[i] + b[j];
sort(ab,ab+h);
for (int i = 0;i < s;i++)
{
int flag = 0;
for (int j = 0;j < m;j++)
{
int tmp = x[i] - c[j];
if (myfind(tmp,h))
flag = 1;
}
if (flag)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
POJ 3273 : MONTHLY EXPENSE
题意:
给出n个数,要求把这n个数分成m个部分,使得每个部分的数的和的最大值最小。
思路:
二分+贪心,套路。
代码:
#include <stdio.h>
int n,m;
int cost[100010];
int solve(int money)
{
int tmp = 0,_if = 1;
for (int i = 0;i < n;i++)
{
if (tmp + cost[i] <= money) tmp += cost[i];
else
{
tmp = 0;
_if++;
i--;
}
}
return _if <= m;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 0;i < n;i++)
scanf("%d",&cost[i]);
int lb = -1,ub = 0;
for (int i = 0;i < n;i++)
{
if (cost[i] > lb)
lb = cost[i];
ub += cost[i];
}
while(lb < ub)
{
int mid = (lb + ub) / 2;
if (solve(mid)) ub = mid;
else lb = mid + 1;
}
printf("%d\n",ub);
return 0;
}
poj3258 river hopscotch
题意:
最大化最小值。有n个石头,两个岸,问可以移走m个石头的情况下两个障碍物之间距离最小的最大值是多少。
思路:
二分。QAQ我只能把这题记住了。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[50005];
int m,n,L;
int meet(int dis)
{
int cnt = 0;
int last = 0;
for (int i = 1;i <= n+1;i++)
{
if (dis >= (a[i]-a[last]))
{
cnt++;
}
else
{
last = i;
}
}
return cnt;
}
int main()
{
scanf("%d%d%d",&L,&n,&m);
a[0] = 0;
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]);
a[n+1] = L;
sort(a+1,a+n+1);
int low = 0,high = L;
while (low <= high)
{
int mid = (low + high) >> 1;
if (meet(mid) <= m) low = mid + 1;
else high = mid - 1;
}
printf("%d\n",low);
return 0;
}