旅游

当前位置:手机版美高梅网站 > 旅游 > 选料酒馆

选料酒馆

来源:http://www.best-sclae.com 作者:手机版美高梅网站 时间:2019-12-02 19:15

★★   输入文件:hotel.in   输出文件:hotel.out   轻便相比较
时刻约束:1 s   内部存款和储蓄器约束:128 MB

P1311 选拔酒店

【难点陈说】

题目陈说

呼伦贝尔河边有n 家很有风味的酒店,酒馆依照其地方顺序从 1 到n 编号。每家酒馆都固守某风流倜傥种色彩进行装点(总共 k 种,用整数 0 ~ k-1 表示),且每家酒店都存在一家咖啡馆,每家咖啡馆均有独家的最低花费。

两位游客一齐去大理观景,他们赏识同一的光泽,又想尝尝五个不相同的酒馆,由此调控分别住在颜色相似的两家旅社中。早晨,他们筹划筛选一家咖啡馆喝咖啡,需要咖啡厅位于五个人住的两家公寓之间(包涵他们住的饭店),且咖啡厅的最低花费不超过p 。

她们想驾驭风华正茂共有些许种接纳留宿的方案,保险清晨得以找到一家最低成本不超过p元的咖啡厅小聚。

眉山河边有n 家很有特点的旅舍,饭店遵照其地方顺序从1 到n 编号。每家商旅都依据某意气风发种色彩实行李装运裱(总共k 种,用整数0 ~ k-1 表示),且每家饭馆都留存一家咖啡馆,每家咖啡厅均有个别的最低花费。
两位游客同盟去邵阳国旅,他们心仪同风度翩翩的光华,又想尝试多少个不等的旅店,因而调整各自住在颜色相符的两家旅馆中。清晨,他们准备筛选一家咖啡厅喝咖啡,须求咖啡厅坐落于多个人住的两家旅馆之间(包罗他们住的饭馆),且咖啡馆的最低开销不超过p。
她们想精晓一同有稍稍种选用住宿的方案,保险凌晨能够找到一家最低花费不超越p元的咖啡厅小聚。

输入输出格式

输入格式:

 

输入文件hotel.in,共n+1 行。

率先行八个整数n ,k ,p,每八个整数之间用一个空格隔开分离,分别表示饭店的个数,色调的数码和能经受的最低花费的最高值;

接下去的n 行,第 i+1 行多少个整数,之间用二个空格隔断,分别代表 i 号酒店的装裱色调护医治i 号旅社的咖啡店的最低花费。

 

出口格式:

 

出口文件名叫hotel.out 。

出口唯有生机勃勃行,二个整数,表示可选的留宿方案的总的数量。

 

【输入】
输入文件hotel.in,共n+1 行。
先是行四个整数n,k,p,每五个整数之间用一个空格隔绝,分别代表商旅的个数,色调的数据和能接纳的最低花费的最高值;
接下去的n 行,第i+1 行五个整数,之间用二个空格隔断,分别表示i 号饭馆的装饰色调养i 号饭店的咖啡馆的最低花费。

输入输出样例

输入样例#1:

5 2 3 
0 5 
1 3 
0 2 
1 4 
1 5 

出口样例#1:

3

【输出】
出口文件名为hotel.out。

说明

【输入输出样例表明】

图片 1

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。

输出独有风流倜傥行,三个偏分头,表示可选的留宿方案的总的数量。

code

【输入输出样例1】

code1

强力+优化得了60分

 1 #include<cstdio>
 2 
 3 const int N = 200100;
 4 int mo[N];
 5 int col[N];
 6 int sum[N];
 7 int n,k,p,ans;
 8 
 9 int main()
10 {
11     scanf("%d%d%d",&n,&k,&p);
12     for(int i=1;i<=n;++i)
13     {
14         scanf("%d%d",&col[i],&mo[i]);
15         if(mo[i]<=p) sum[i]=sum[i-1]+1;
16         else sum[i] = sum[i-1];
17     }
18     for(int i=1;i<=n;++i)
19     {
20         for(int j=i+1;j<=n;++j)
21         {
22             if(col[i]==col[j] && sum[j]-sum[i-1]!=0) ans++;
23         }
24     }
25     printf("%d",ans);
26 }

 

hotel.in

code2

 

新兴见大佬那样写的

思路是:

当找到二个酒店时,若是他左手有八个符合须要的咖啡厅,那么再往右侧看,若是有一个颜料
相似的饭馆,那么那正是意气风发种办法,那么只要以那个右侧的酒店往左,将具有在左侧而且颜色与之相
同的饭馆数相加,就能够得出全数的住宿方法了。那么用这一个法子,用全数的对应点对应过去,就能够最快的时日内找
出所用的酒店了。
用s数组一时记录当前相近颜色的小吃摊现身的次数,也便是找的对应点有时记录。
用c数组是记录大器晚成致种颜色中的商旅所现身的终极叁回的岗位;
用num数组记录后生可畏致种颜色的舞厅的现身次数,

 1 #include<cstdio>
 2 const int N = 200100;
 3 int n,k,p,col,mon,now,ans;
 4 int num[N],s[N],c[N];
 5 int main()
 6 {
 7     scanf("%d%d%d",&n,&k,&p);
 8     for(int i=1;i<=n;++i)
 9     {
10         scanf("%d%d",&col,&mon);
11         if(mon<=p) now = i;
12         if(now>=c[col]) s[col] = num[col];
13         c[col] = i;
14         ans += s[col];
15         num[col]++;
16     }
17     printf("%d",ans);    
18     return 0;
19 }

 

5 2 3
0 5
1 3
0 2
1 4
1 5

hotel.out

3

【输入输出样例表达】

客栈编号
色调 0 1 0 1 1
最低消费 5 3 2 4 5

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, K≤50,0≤P≤100,

 

暴力60分:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 
 7 const int N = 200010;
 8 using namespace std;
 9 
10 int v[N];
11 int sd[N];
12 int a[N];
13 
14 inline int read()
15 {
16     int x=0,f=1;
17     char c=getchar();
18     while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();}
19     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
20     return x*f;
21 }
22 
23 int main()
24 {
25     freopen("hotel.in","r",stdin);
26     freopen("hotel.out","w",stdout);
27     int n=read();
28     int m=read();
29     int p=read();
30     sd[1]=read();
31     v[1]=read();
32     for(int i=2;i<=n;i++)
33     {
34         sd[i]=read();
35         v[i]=read();
36     }
37     int Answer=0;
38     
39     for(int i=1;i<n;i++)
40         for(int j=i+1;j<=n;j++)
41         {
42             if(sd[i]!=sd[j])continue ;
43             int minn=999999;
44             for(int k=i;k<=j;k++)
45                 minn=min(minn,v[k]);
46             if(minn<=p)Answer++;
47         }
48         
49     printf("%d",Answer);
50     return 0;
51 }

 

NB代码:(by )

思路是:

当找到三个公寓时,如若她左臂有二个适合要求的咖啡馆,那么再往左侧看,要是有一个颜料
意气风发致的旅社,那么那正是生机勃勃种艺术,那么大器晚成旦以这么些右侧的公寓往左,将有所在右边手並且颜色与之相
同的旅舍数相加,就会得出全体的下榻方法了。那么用那一个办法,用具备的对应点对应过去,就能够最快的光阴内找
出所用的舞厅了。
用s数组有的时候记录当前肖似颜色的酒店现身的次数,也等于找的对应点不常记录。
用c数组是记录同风流洒脱种颜色中的商旅所现身的末段二回的职责;
用num数组记录同风度翩翩种颜色的饭馆的现身次数,

 

 1 #include<cstdio>
 2 
 3 const int N = 200100;
 4 
 5 int n,k,p,col,mon,now,ans;
 6 
 7 int num[N],s[N],c[N];
 8 
 9 int main()
10 {
11     scanf("%d%d%d",&n,&k,&p);
12     
13     for(int i=1;i<=n;++i)
14     {
15         scanf("%d%d",&col,&mon);
16         if(mon<=p) now = i;
17         if(now>=c[col]) s[col] = num[col];
18         c[col] = i;
19         ans += s[col];
20         num[col]++;
21     }
22     
23     printf("%d",ans);    
24     return 0;
25 }

 

本文由手机版美高梅网站发布于旅游,转载请注明出处:选料酒馆

关键词:

上一篇:没有了

下一篇:没有了