区间选点问题(P233)

-方法：

把所有区间按b从小到大排序（b相同时a从大到小排序），则如果出现区间包含的情况，小区间一定排在前面。第一个区间应该取最后一个点。

-练习(POJ1328)：

更自然的方法：

每个岛屿都有这样的最左和最右可被侦测坐标。
根据贪婪的思想，每次都应该将最右可被侦测坐标作为衡量标准。
假定当前的岛屿为cur，当前的下一个为next。
1.如果next的最左可被侦测坐标比cur的最右都大的话，只能再设一个雷达来侦测next了。

2.如果next的最左可被侦测坐标比cur的最右小，这时会有两种情况。
A.next最右 < cur最右
B.next最右 >= cur最右
对于B情况,我们可以直接侦测到next了, 可以找next的next了.
对于A情况,也就等价于next包含于cur, 这样就应该把next的右最为衡量标准了.
因为这样可以左移最右坐标, 可以让可能更多的岛屿被侦测到(他们的最左与衡量标准有更多的交集)

-教训：

注意中间变量t是double啊啊啊啊啊…

贪心(POJ2109)

方法一（用double）：

k=pow(p,1/n);

类型 长度 (bit) 有效数字 绝对值范围
float 32 6~7 10^(-37) ~ 10^38
double 64 15~16 10^(-307) ~10^308
long double 128 18~19 10^(-4931) ~ 10 ^ 4932

首先需要明确：double类型虽然能表示10^(-307) ~ 10^308, （远大于题意的1<=p<10101这个范围）,但只能精确前16位，因此必须慎用！

方法二（高精度运算+二分查找+快速幂）：

方法三（贪心法）：黑人问号？？？

贪心(POJ2586)

方法一（枚举）：

根据前五个月的情况分五种情况。**

方法二（贪心）：

先将每个月都当成盈利，从1月开始，算5个月的总和，假如是盈利，把最后一个月设成亏损（最后一个月取到的次数最多），再算5个月总和，要是还是盈利，继续依次设置下去。要注意的是，假如一个月盈利大于4个月亏损总和，就只能全亏了。

线段的重叠（51nod 1091）

先排序，起点升序，终点降序，因为贪心。然后用两重循环，把每一条线段当成基准，然后对之后的每一条线段根据完全重叠和重叠部分进行讨论，线扫一遍。

struct st
{
    int s;
    int e;
}d[50010],temp;
bool cmp(st x,st y)
{
    if(x.s!=y.s)return x.s<y.s;
    return x.e>y.e;
}
int main()
{
    int n,MAX,l,i,j,sign;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d%d",&d[i].s,&d[i].e);
    sort(d,d+n,cmp);
    MAX=0;sign=0;
    for(i=0;i<n;i++)
    {
        temp.s=d[i].s;temp.e=d[i].e;
        for(j=i+1;j<n;j++)
        {
            if(d[j].s<=temp.e)
            {
                if(d[j].e>=temp.e)
                {
                    l=temp.e-d[j].s;
                    MAX=max(MAX,l);
                    sign++;
                    break;
                }
                else
                {
                    l=d[j].e-d[j].s;
                    MAX=max(MAX,l);
                    sign++;
                }
            }
            else break;
        }
    }
    if(sign==0)printf("0\n");
    else printf("%d\n",MAX);
    return 0;
}