2014
03-03

# Soda Surpler

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

#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;
}

#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;
}

1. “等我长大了，我自己捉人吃。”这点倒是和我们小时候想吃东西爸妈不给吃（比如太甜啦太贵啦不健康啦之类）的时候想得差不多……