首页 > 代码库 > NOIP 2011 hotel
NOIP 2011 hotel
描述
丽江河边有n家很有特色的客栈,客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰(总共k种,用整数0~ k-1表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过p。
他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。
格式
输入格式
第一行三个整数n,k,p,每两个整数之间用一个空格隔开,分别表示客栈的个数,色调的数目和能接受的最低消费的最高值;
接下来的n行,第i+1行两个整数,之间用一个空格隔开,分别表示i号客栈的装饰色调和i号客栈的咖啡店的最低消费。
输出格式
输出只有一行,一个整数,表示可选的住宿方案的总数。
样例1
样例输入1
5 2 30 51 30 21 41 5
Copy
样例输出1
3
Copy
限制
1s
提示
对于30%的数据,有n≤100;
对于50%的数据,有n≤1,000;
对于100%的数据,有2≤n≤200,000,0<k≤50,0≤p≤100,0≤最低消费≤100。
来源
NOIp2011提高组Day1第二题
有O(n*k+n) ,O(n*k)和O(n)做法
下面是O(n)的
last[i]=j 表示当前颜色为i的 所有客栈中,最后一个的是j
lastcostpos 表示当前所有客栈中,最后一个消费<=p的客栈
sumx[i]=j 表示当前颜色为i的客栈共有j个
sum[i]=j 表示当前与 颜色为i的这个客栈 可以组成的合法方案数
1 #include<cstdio> 2 #include<iostream> 3 #define MAXN 200010 4 5 using namespace std; 6 7 int n,p,k,ans=0; 8 9 int color,cost,lastcostpos;10 11 int last[MAXN],sum[MAXN],sumx[MAXN];12 13 inline void read(int&x) {14 int f=1;x=0;char c=getchar();15 while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}16 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}17 x=x*f;18 }19 20 int main() {21 read(n);read(k);read(p);22 for(int i=1;i<=n;i++) {23 read(color);read(cost);24 if(cost<=p) lastcostpos=i;25 if(last[color]<=lastcostpos) sum[color]=sumx[color];26 sumx[color]++;27 last[color]=i;28 ans+=sum[color];29 }30 printf("%d\n",ans);31 return 0;32 33 }
NOIP 2011 hotel
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。