首页 > ACM题库 > HDU-杭电 > HDU 3884-Hinanai Tenshi’s peach garden-贪心-[解题报告]HOJ
2015
04-13

HDU 3884-Hinanai Tenshi’s peach garden-贪心-[解题报告]HOJ

Hinanai Tenshi’s peach garden

问题描述 :

Hinanai Tenshi is managing a peach garden in Bhavagra. Due to the careful watch of Tenshi, the peach garden becomes a great view of Bhavagra. Once a famous person whose ear is pretty big said when visiting the garden: “This is peach garden?”

Another harvest season has come, Tenshi wants to move all the peaches to one point, so Tenshi sent her sidekick, Nagae Iku, to do this mission. However, Iku was only able to move all peaches to N points before she was sent to other missions…The remaining work can only be done by Tenshi herself.

Now Iku has moved the peaches to N points, the ith point is (xi, 0), which has pi peaches on it. Moving one peach from one point to another point costs the distance between these two points, two peaches is double the cost and etc. Tenshi wants to move as many peaches to one point as possible without costing too much, so Tenshi wants to know how many peaches can she move to one point without total costing over K.

CS and Sugar

输入:

Multiple test cases (no more than 20), for each case:
The first line contains two integers N and K (0<N<=10^4, 0<=K<=10^18).
Following N lines, each line contains two integers xi and pi (0<=xi<10^9, 0<pi<10^4).
Input terminates with EOF.

输出:

Multiple test cases (no more than 20), for each case:
The first line contains two integers N and K (0<N<=10^4, 0<=K<=10^18).
Following N lines, each line contains two integers xi and pi (0<=xi<10^9, 0<pi<10^4).
Input terminates with EOF.

样例输入:

3 1
0 1
1 1
2 1

样例输出:

2

枚举每个点,把最近的点拉过来,每次左右两边找最近,直到超过步数。。。

#include <stdio.h>
#include <stdlib.h>
#define tt int
#define bt __int64
typedef struct {
    int x;
    int y;
}ppp;

ppp pp[10005];
inline bt max(bt a,bt b) 
{
    return a>b?a:b;
}

inline tt min(tt a,tt b)
{
    return a<b?a:b;
}

tt cmp(const void *p,const void *q)
{
    ppp *p1,*p2;
    p1=(ppp *)p;
    p2=(ppp *)q;
    return p1->x - p2->x;
}

int main()
{
    int n,i,j,k,t;
    bt m;
    bt tm;
    int lf,rf;
    int pos,pos2;
     bt sum;
     bt temp;
     bt temp2;
    while(scanf("%d%I64d",&n,&m)!=EOF)
    {
        sum=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&pp[i].x,&pp[i].y);
        }
        qsort(pp,n,sizeof(pp[0]),cmp);
        for(i=0;i<n;i++)
        {    
            temp=pp[i].y;
            tm=m;
            lf=i-1;
            rf=i+1;
            while((lf!=-1 || rf!=n) && tm!=0)
            {
                if(lf==-1) 
                {
                    pos=rf;
                    if(tm>((bt)(pp[pos].x-pp[i].x))*pp[pos].y)
                    {
                        temp+=pp[pos].y;
                        tm-=((bt)(pp[pos].x-pp[i].x))*pp[pos].y;
                    }
                    else
                    {
                        temp+=tm/(pp[pos].x-pp[i].x);
                        break;
                    }
                    rf++;
                }
                else if(rf==n)
                {
                    pos=lf;
                    if(tm>((bt)(pp[i].x-pp[pos].x))*pp[pos].y)
                    {
                        temp+=pp[pos].y;
                        tm-=((bt)(pp[i].x-pp[pos].x))*pp[pos].y;
                    }
                    else
                    {
                        temp+=tm/(pp[i].x-pp[pos].x);
                        break;
                    }
                    lf--;
                }
                else 
                {
                    if(pp[rf].x-pp[i].x > pp[i].x - pp[lf].x)
                    {
                        pos=lf;
                        if(tm>((bt)(pp[i].x-pp[pos].x))*pp[pos].y)
                        {
                            temp+=pp[pos].y;
                            tm-=((bt)(pp[i].x-pp[pos].x))*pp[pos].y;
                        }
                        else
                        {
                            temp+=tm/(pp[i].x-pp[pos].x);
                            break;
                        }
                        lf--;
                    }
                    else 
                    {
                        pos=rf;
                        if(tm>((bt)(pp[pos].x-pp[i].x))*pp[pos].y)
                        {
                            temp+=pp[pos].y;
                            tm-=((bt)(pp[pos].x-pp[i].x))*pp[pos].y;
                        }
                        else
                        {
                            temp+=tm/(pp[pos].x-pp[i].x);
                            break;
                        }
                        rf++;
                    }
                }
            }
            sum=sum>temp?sum:temp;
        }
        printf("%d\n",sum);
    }
    return 0;
}

参考:http://www.cnblogs.com/zjh10/articles/2212086.html


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”