Description
麗江河邊有n家很有特色的客棧，客棧按照其位置順序從1到n編號。每家客棧都按照某一種色調(diào)進(jìn)行裝飾（總共k種，用整數(shù)0 ~ k-1表示），且每家客棧都設(shè)有一家咖啡店，每家咖啡店均有各自的最低消費。 兩位游客一起去麗江旅游，他們喜歡相同的色調(diào)，又想嘗試兩個不同的客棧，因此決定分別住在色調(diào)相同的兩家客棧中。晚上，他們打算選擇一家咖啡店喝咖啡，要求咖啡店位于兩人住的兩家客棧之間（包括他們住的客棧），且咖啡店的最低消費不超過p。 他們想知道總共有多少種選擇住宿的方案，保證晚上可以找到一家最低消費不超過p元的咖啡店小聚。

Input
輸入文件hotel.in，共n+1行。 第一行三個整數(shù)n，k，p，每兩個整數(shù)之間用一個空格隔開，分別表示客棧的個數(shù)，色調(diào)的數(shù)目和能接受的最低消費的最高值； 接下來的n行，第i+1行兩個整數(shù)，之間用一個空格隔開，分別表示i號客棧的裝飾色調(diào)和i號客棧的咖啡店的最低消費。

Output
輸出只有一行，一個整數(shù)，表示可選的住宿方案的總數(shù)。

Sample Input
5 2 3
0 5
1 3
0 2
1 4
1 5

Sample Output
3

Data Constraint

Hint
2人要住同樣色調(diào)的客棧，所有可選的住宿方案包括：住客棧①③，②④，②⑤，④⑤，但是若選擇住4、5號客棧的話，4、5號客棧之間的咖啡店的最低消費是4，而兩人能承受的最低消費是3元，所以不滿足要求。因此只有前3種方案可選。

對于30%的數(shù)據(jù)，有n≤100； 對于50%的數(shù)據(jù)，有n≤1,000； 對于100%的數(shù)據(jù)，有2≤n≤200,000，0<k≤50，0≤p≤100， 0≤最低消費≤100。

.
.
.
.
.
分析
暴力

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k,p; int a[51],b[51],c[200001],m[200001],wz[51][200001],num[51];int main() {scanf("%d%d%d",&n,&k,&p);memset(a,0,sizeof(a));memset(b,0,sizeof(b));for (int i=1;i<=n;i++){scanf("%d%d",&c[i],&m[i]);if (a[c[i]]==0) a[c[i]]=i;b[c[i]]=i;num[c[i]]++;wz[c[i]][num[c[i]]]=i;}long long sum=0;for (int i=0;i<=k;i++){int l=a[i],r=b[i];for (int j=1;j<=num[i]-1;j++){int bz=0;for (int k=j+1;k<=num[i];k++){int l1=wz[i][j],r1=wz[i][k];for (int o=l1;o<=r1;o++)if (m[o]<=p){bz=k;break;}if (bz!=0) break;}if (bz!=0){int x=num[i]-bz+1;sum+=x;}}}printf("%lld",sum);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10292783.html

總結(jié)

以上是生活随笔為你收集整理的选择客栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。