@goldhjy
2017-01-18T07:23:41.000000Z
字数 8585
阅读 779
二分/三分
Now, here is a fuction:
F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)
Can you find the minimum value when x is between 0 and 100.
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has only one real numbers Y.(0 < Y <1e10)
Output
Just the minimum value (accurate up to 4 decimal places),when x is between 0 and 100.
Sample Input
2
100
200
Sample Output
-74.4291
-178.8534
题意：一道数学题，求x在0-100之间时，这二个方程的最小值。
思路：首先，高数上说过，一个方程的最小值是在求导的式子=0是取得最值。说白了变完过后的求导式子去搜索那个值最小，这里用的是一个二分查找，会少很大的复杂度。
#include <bits/stdc++.h>
using namespace std;
double serch(double mid);
int main()
{
int T;
double y,right,left,mid;
scanf("%d",&T);
while(T--)
{
right=100,left=0;
scanf("%lf",&y);
for(int i=1;i<=100;i++)
{
mid=(right+left)/2;
if(serch(mid)==y)
break;
else if(serch(mid)>y)
right=mid;
else
left=mid;
}
printf("%0.4lf\n",6*pow(mid,7)+8*pow(mid,6)+7*pow(mid,3)+5*mid*mid-y*mid);
}
return 0;
}
double serch(double x)
{
return 42*pow(x,6)+48*pow(x,5)+21*x*x+10*x;
}
B - Can you find it? HDU - 2141
-------------------------------
Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.
Input
There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.
Output
For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".
Sample Input
3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10
Sample Output
Case 1:
NO
YES
NO
题意：给你三组数，每一组你都必须取一个。然后后面会给你一些数字，如果，刚才的三组数中，有可以结合成这个数字，就是YES，如果不能就是NO。
思路：我们先把给的这个数字去减去三组数字中的一组其中的一个数字。把其他两组的数字先组合到一个数组中去。这个数字去减去三组数字中的一组其中的这个数字拿去和我们2组合出来的这组数据对比，就是一个二分查找。如果有就YES。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int searcher(int pp);
int l,n,m,x=0,s,tp,casex=1;
int a[505],b[505],c[505],d[250005];
int main()
{
while(scanf("%d %d %d",&l,&n,&m)!=EOF)
{
x=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]);
}
for(int i=0;i<l;i++)
for(int j=0;j<n;j++)
{
d[x++]=a[i]+b[j];
}
x--;
sort(d,d+x);
scanf("%d",&s);
printf("Case %d:\n",casex++);
while(s--)
{
scanf("%d",&tp);
if(searcher(tp))
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
int searcher(int pp)
{
for(int i=0;i<m;i++)
{
int ppp=pp-c[i];
int p=lower_bound(d,d+x,ppp)-d;
if(p==0)
if(d[p]!=ppp)
continue;
else
return 1;
else
{
if(d[p]!=ppp&&d[p-1]!=ppp)
continue;
else
return 1;
}
}
return 0;
}
Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.
FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.
FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.
Input
Line 1: Two space-separated integers: N and M
Lines 2.. N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day
Output
Line 1: The smallest possible monthly limit Farmer John can afford to live with.
Sample Input
7 5
100
400
300
100
500
101
400
Sample Output
500
Hint
If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.
题意：给你N个数字。你可以进行M次划分。要求是输出你能划分出来的每一组数据之和的的最小值。
思路：先把这些数据的最大值找出来，因为答案不可能小于这个最大值。然后从第一个开始，依次查找，如果这个数加上下一个数会小于我们的之前找的最大值，就加上，如果大于，就不要而且计数要加上1.我们再从这个数开始找，再像上面那样进行。这个计数器初始值是1，这个计数器相当于隔板，我们只能进行M-1次隔板。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int sercher(int mid);
int a[100005];
int M,N;
int main()
{
while(~scanf("%d%d",&N,&M))
{
int left=0,right=0,mid;
for(int i=0;i<N;i++)
{
scanf("%d",&a[i]);
left=max(a[i],left);
right+=a[i];
}
while(left<=right)
{
mid=(left+right)/2;
if(sercher(mid))
right=mid-1;
else
left=mid+1;
}
printf("%d\n",mid);
}
return 0;
}
int sercher(int mid)
{
int sum=0,cnt=1;
for(int i=0;i<N;i++)
{
if(sum+a[i]<=mid)
sum+=a[i];
else
{
sum=a[i];
cnt++;
}
}
if(cnt>M)
return 0;
else
return 1;
}
Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).
To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.
Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).
FJ wants to know exactly how much he can increase the shortest distance before he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.
Input
Line 1: Three space-separated integers: L, N, and M
Lines 2.. N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.
Output
Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks
Sample Input
25 5 2
2
14
11
21
17
Sample Output
4
Hint
Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).
题意：我们的牛要从0跳到L位置。中间有N个位置可以跳，我们还可以从N个位置中去掉M个位置，要求是我们的牛每一次跳的距离必须是尽量大，输出我们的牛每天跳的距离的最小值。
思路：这个问题在于我们有时候去掉了一块石头相应的会减少两个最小的距离，所以，不可以把每一块石头之间的距离算出来然后减去最小的前两个，还是只有搜索这一条路，这次搜索的范围在最小值和L之间。二分找，枚举他们之间的这些数据。只要满足从开始跳到最后减去的石头数<=M就行，
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int a[50005];
int main()
{
int M,N,L,sum,cnt,maxn,minn,mid;;
scanf("%d%d%d",&L,&N,&M);
a[0]=0,a[N+1]=L;
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
}
N++;
sort(a,a+N);
maxn=L;minn=L;
for(int j=1;j<=N;j++)
minn=min(minn,a[j]-a[j-1]);
while(maxn>=minn)
{
mid=(minn+maxn)/2;
sum=0,cnt=0;
for(int i=1;i<=N;i++)
{
if((sum+=a[i]-a[i-1])<=mid)
cnt++;
else
sum=0;
}
if(cnt<=M)
minn=mid+1;
else
maxn=mid-1;
}
printf("%d\n",minn);
return 0;
}
We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.
Output
Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.
Sample Input
1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110
Sample Output
0.649
题意：给你B和P要求每一个部件都要取一个。要求B/P最大。平时全部部件加起来之和。B是我们取得每一个部件的最小值。
思路：和之前那道题的思路差不多，还是枚举搜索。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
int b;
int p;
};
node pp[105][105];
int m[105];
int cmp(struct node r,struct node t)
{
return r.p<t.p;
}
int main()
{
int t,n,x,k,p2,b2;
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&m[i]);
for(int j=0;j<m[i];j++)
{
scanf("%d %d",&pp[i][j].b,&pp[i][j].p);
}
sort(&pp[i][0],&pp[i][0]+m[i],cmp);
}
b2=0,p2=0,ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m[i];j++)
{
b2=pp[i][j].b;
p2=pp[i][j].p;
for(k=0;k<n;k++)
{
if(k==i)
continue;
for(x=0;x<m[k];x++)
{
if(b2<=pp[k][x].b)
break;
}
if(x>=m[k])
break;
p2+=pp[k][x].p;
}
if(k<n)
continue;
if(ans<1.0*b2/p2)
ans=1.0*b2/p2;
}
}
printf("%0.3f\n",ans);
}
return 0;
}