洛谷P1311 选择客栈
2024-08-24 23:53:33
P1311 选择客栈
题目描述
丽江河边有n 家很有特色的客栈,客栈按照其位置顺序从 1 到n 编号。每家客栈都按照某一种色调进行装饰(总共 k 种,用整数 0 ~ k-1 表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过 p 。
他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。
输入输出格式
输入格式:
输入文件hotel.in,共n+1 行。
第一行三个整数n ,k ,p,每两个整数之间用一个空格隔开,分别表示客栈的个数,色调的数目和能接受的最低消费的最高值;
接下来的n 行,第 i+1 行两个整数,之间用一个空格隔开,分别表示 i 号客栈的装饰色调和i 号客栈的咖啡店的最低消费。
输出格式:
输出文件名为hotel.out 。
输出只有一行,一个整数,表示可选的住宿方案的总数。
输入输出样例
输入样例#1:
5 2 3
0 5
1 3
0 2
1 4
1 5
输出样例#1:
3
说明
【输入输出样例说明】
2 人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,但是若选择住4 、5 号客栈的话,4 、5 号客栈之间的咖啡店的最低消费是4 ,而两人能承受的最低消费是3 元,所以不满足要求。因此只有前 3 种方案可选。
【数据范围】
对于30% 的数据,有 n ≤100;
对于50% 的数据,有 n ≤1,000;
对于100%的数据,有 2 ≤n ≤200,000,0<k ≤50,0≤p ≤100 , 0 ≤最低消费≤100。
#include<iostream>
#include<cstdio>
#define maxn 200010
using namespace std;
int n,k,p,map[][maxn],sum[maxn];
long long ans;
int main(){
scanf("%d%d%d",&n,&k,&p);
int x,y;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
x++;
map[x][++map[x][]]=i;
if(y<=p)sum[i]=sum[i-]+;
else sum[i]=sum[i-];
}
for(int i=;i<=k;i++)
for(int lg=;lg<=map[i][];lg++)
for(int rg=lg+;rg<=map[i][];rg++){
int l=map[i][lg],r=map[i][rg];
if(sum[r]-sum[l-])ans++;
}
cout<<ans;
}
70分 前缀和
#include<iostream>
#include<cstdio>
#define maxn 200010
using namespace std;
int n,k,p,map[][maxn],sum[maxn];
long long ans;
int main(){
scanf("%d%d%d",&n,&k,&p);
int x,y;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
x++;
map[x][++map[x][]]=i;
if(y<=p)sum[i]=sum[i-]+;
else sum[i]=sum[i-];
}
for(int i=;i<=k;i++)
for(int lg=;lg<=map[i][];lg++)
for(int rg=lg+;rg<=map[i][];rg++){
int l=map[i][lg],r=map[i][rg];
if(sum[r]-sum[l-]){
ans+=map[i][]-rg+;
break;//优化在这里
}
}
cout<<ans;
}
100分 前缀和+小优化
最新文章
- 查询表结构sql
- 根据字体计算CGRect
- entity framework自动迁移
- 关于Tcp,为什么一定要进行三次握手呢?
- ogistic regression (逻辑回归) 概述
- javascrpt随笔
- DJANGO变动库的一次真实手动经历
- c#后台修改前台DOM的css属性
- Linux下通过ODBC连接sqlserver
- JSP HTML区别
- jQuery 选择器和JavaScript 选择器的技巧与异常原因
- Java中SimpleDateFormat用法详解
- PHP防SQL注入攻击
- String对象常量池特性对synchronized对象的影响
- 容器化 — 基于Docker技术容器云
- Ubuntu 开启SSH服务以及有关设置:安装,指定端口号、免密登录、远程拷贝
- poj3723_Conscription
- drf1 rest &; restful规范
- zoj 3195(LCA加强版)
- Android 使用第三方登录(QQ和新浪微博)
热门文章
- 分享知识-快乐自己:JS 检查元素是否含有某种css样式
- 给手机发验证码 综合使用 (忘记密码处理 php发验证码 重置用户密码)
- 重拾安卓_01_安卓开发环境搭建(android studio)
- hdu-5651 xiaoxin juju needs help(数学+gcd约分求阶乘)
- Post提交和Get提交的区别
- 【二叉查找树】01不同的二叉查找树的个数【Unique Binary Search Trees】
- 无旋Treap - BZOJ1014火星人 &; 可持久化版文艺平衡树
- MYSQL root密码修改找回命令
- POJ3417Network
- “Hello World”—— 第一个汇编程序