首页 > ACM题库 > HDU-杭电 > HDU 3139-Soda Surpler[解题报告]HOJ
2014
03-03

HDU 3139-Soda Surpler[解题报告]HOJ

Soda Surpler

问题描述 :


Coconuts

Tim is an absolutely obsessive soda drinker, he simply cannot get enough. Most annoyingly though, he almost never has any money, so his only obvious legal way to obtain more soda is to take the money he gets when he recycles empty soda bottles to buy new ones. In addition to the empty bottles resulting from his own consumption he sometimes find empty bottles in the street. One day he was extra thirsty, so he actually drank sodas until he couldn’t afford a new one.

输入:

Three non-negative integers e, f, c, where e < 1000 equals the number of empty soda bottles in Tim’s possession at the start of the day, f < 1000 the number of empty soda bottles found during the day, and 1 < c < 2000 the number of empty bottles required to buy a new soda.

输出:

Three non-negative integers e, f, c, where e < 1000 equals the number of empty soda bottles in Tim’s possession at the start of the day, f < 1000 the number of empty soda bottles found during the day, and 1 < c < 2000 the number of empty bottles required to buy a new soda.

样例输入:

9 0 3
5 5 2

样例输出:

4
9

题意:给p、 d分别代表每个旅馆的价钱和需要走的距离,问能最多选几个旅馆但需要满足以下条件

被选中的旅馆 i 的情况下,不能存在一个旅馆其价钱和距离都比i 的小

思路:我们可以把每种价钱的最短距离保存起来,之后处理时拿到某一个旅馆,就判断前面是否存在价钱和距离都比它小的情况,如果满足就放弃它,否则取它(前提:已经排好序的,先按价钱从小到大排,如果价钱相等,就按距离从小到大排)

因为那个距离和价钱是>=0的,所以对于0的处理情况一直不行,我之前采用下标为0的,但是WA了,我也不明白为什么WA,现在用了下标1的,A了!真不解

代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
struct node
{
    int p,d;
} s[10010];
int dis[10030];//保存每种价格的最短距离
int ff[10010];
int f[10010][20];
bool cmp(node a,node b)
{
    if(a.p==b.p)return a.d<b.d;
    return a.p<b.p;
}
void RMQ()
{
    for(int i=1; i<=10010; i++)
        f[i][0]=dis[i];
    int t=floor(log((double)10010)/log(2.0));
    for(int j=1; j<=t; j++)
    {
        for(int i=1; i+(1<<j)-1 <= 10010; i++)
        {
            int s1=f[i][j-1];
            int s2=f[i+(1<<(j-1))][j-1];
            f[i][j]=s1<s2?s1:s2;
        }
    }
}
int query(int s,int e)
{
    int k=0;
    while((1<<(k+1))< e-s+1)
        k++;
    int s1=f[s][k];
    int s2=f[e-(1<<k)+1][k];
    return s1<s2?s1:s2;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(ff,0,sizeof(ff));
        for(int i=1; i<=10030; i++)
            dis[i]=1000000;
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&s[i].p,&s[i].d);
            if(dis[s[i].p+1]> s[i].d)
                dis[s[i].p+1]=s[i].d;
        }
        sort(s+1,s+n+1,cmp);
        RMQ();
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            if(s[i].p==0)
            {
                ans++;
                continue;
            }
            int mm=query(1,s[i].p);
            if(mm < s[i].d)
                ff[i]=1;
            else
                ans++;
        }
        printf("%d\n",ans);
        for(int i=1; i<=n; i++)
        {
            if(ff[i]==0)
                printf("%d %d\n",s[i].p,s[i].d);
        }
    }
    return 0;
}


路过的高手可以帮我看一下这个代码我WA了:

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
struct node
{
    int p,d;
} s[10010];
int dis[10030];//保存每种价格的最短距离
int ff[10010];
int f[10010][20];
bool cmp(node a,node b)
{
    if(a.p==b.p)return a.d<b.d;
    return a.p<b.p;
}
void RMQ()
{
    for(int i=0;i<=10010;i++)
    f[i][0]=dis[i];
    int t=floor(log((double)10010)/log(2.0));
    for(int j=1;j<=t;j++)
    {
        for(int i=0;i+(1<<j)-1 <10010;i++)
        {
            int s1=f[i][j-1];
            int s2=f[i+(1<<(j-1))][j-1];
            f[i][j]=s1<s2?s1:s2;
        }
    }
}
int query(int s,int e)
{
    int k=0;
    while((1<<(k+1)) < e-s+1)
    k++;
    int s1=f[s][k];
    int s2=f[e-(1<<k)+1][k];
    return s1<s2?s1:s2;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(ff,0,sizeof(ff));
        for(int i=0; i<=10030 ; i++)//直接让距离从0开始
            dis[i]=1000000;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&s[i].p,&s[i].d);
            if(dis[s[i].p]> s[i].d)
                dis[s[i].p]=s[i].d;
        }
        sort(s,s+n,cmp);
        RMQ();
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(s[i].p==0)
            {
                ans++;
                continue;
            }
            int mm=query(0,s[i].p-1);//-1是保证从价钱小于s[i].p中找情况
            if(mm<s[i].d)
            ff[i]=1;
            else
            ans++;
        }
        printf("%d\n",ans);
        for(int i=0;i<n;i++)
        {
            if(ff[i]==0)
            printf("%d %d\n",s[i].p,s[i].d);
        }
    }
    return 0;
}

参考:http://blog.csdn.net/acm18810549519/article/details/10231887