首页 > ACM题库 > HDU-杭电 > hdu 2615 Division-分治-[解题报告]C++
2014
02-12

hdu 2615 Division-分治-[解题报告]C++

Division

问题描述 :

Yifenfei and lemon are good friends, they don’t like Ctw, because Ctw’s name is so worldliness.
One day Lcy give them a lot of jewel. Each jewel has own value. They put the jewels in a line, and don’t swap the position of jewel. In order to division the jewels, they think a lot of ideas. At last, they decide a way to division by voting. First let Ctw to divide the line into two non-empty sublines (each subline express a group of jewel). Second yifenfei will to divide one of sublines and also divide it into two non-empty sublines. Than let lemon to choose one of this three sublines., than yifenfei choose one of remaining subline. At last Ctw hold the last subline..
Every one wants to maximize their own share. But because yifenfei don’t like Ctw, so if there are two divisions let himself get the some value, he will choose the way let Ctw get smaller values.
Assuming every one have full knowledge of each other’s strategies and make their decision optimally.

输入:

The input contains multiple test cases.
Each test case include, first one integers n. (3<=n<=100), express how many jewels.
Next one line include n integers Vi (Vi<2^31). The order of jewel is according the position in the line..

输出:

The input contains multiple test cases.
Each test case include, first one integers n. (3<=n<=100), express how many jewels.
Next one line include n integers Vi (Vi<2^31). The order of jewel is according the position in the line..

样例输入:

4
50 90 10 100
3
5 5 5
9
1 1 1 1 1 1 1 1 1

样例输出:

50
5
2

HOJ 2615 Pie

//题意:有f+1个人分n块披萨,每个人要求分得的面积一样,
//      且披萨只能被切开而不能重新组合,求每个人能分到的最大面积v。
//思路:对于每个确定的v,可以计算出最多能满足的人数p。
//      因此得到一个单调递减的函数关系,并且v的范围也可以确定为0~max(size(i)),i=1...n。(图中)
//      一般要求什么酒对什么进行二分,对某一个面积进行判断,如果满足条件,那么找比这个面积大的满足条件的
//调试:编译的时候出现 undefined reference to [email protected]'  
//     由于把main写成 mian啦
//     这个题貌似很恶心 Pi  还是用反三角函数比较好
//      人数是输入的F+1个儿不是F个他本人也要分       
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define  Pi acos(-1)
#define maxlen 10010
using namespace std;
long long high,mid,low,ans,s[maxlen];
int T,N,i,F;
double r;
bool judge(long long mid)
{
    int i;
    bool  flag;
    long long p = 0;
    for (i = 0; i < N; i++)
        p += s[i] / mid;
    if(p>=F+1)flag=true;//注意这里是f+1
    else flag=false;
    return flag;
}//判断分成这个面积可不可以
int main()
{
    cin >> T;
    while(T--)
    {
        low=0,high=0,ans=0;
        cin >> N >> F;
        memset(s,0,sizeof(s));
        for(i=0; i<N; i++)
        {
            cin >> r;
            s[i]=r*Pi*r*1000000;//先乘以一个大的树,再除回来,怕精度问题
            high+=s[i];
        }
        while(low<=high)
        {
            mid=(low+high)/2;
            if (judge(mid))
            {
                low = mid + 1;
                ans = mid;
            }
            else
                high = mid - 1;
        }
        printf("%.4lf\n", (double)ans/1000000);
    }
    return 0;
}

解题转自:http://blog.csdn.net/hit1110310422/article/details/8535449