題目描述?Description

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

輸入描述?Input Description

共n+1 行。
第一行三個整數 n，k，p，每兩個整數之間用一個空格隔開，分別表示客棧的個數，色調的數目和能接受的最低消費的最高值；
接下來的 n 行，第i+1 行兩個整數，之間用一個空格隔開，分別表示i 號客棧的裝飾色調和i 號客棧的咖啡店的最低消費。

輸出描述?Output Description

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

樣例輸入?Sample Input

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

樣例輸出?Sample Output

3

數據范圍及提示?Data Size & Hint

【輸入輸出樣例說明】

客棧編號	①	②	③	④	⑤
色調?	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。

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<queue> #include<stack> #include<algorithm> #define maxn 200005 #define maxint ~0U>>2 using namespace std; int n,k,p,money[maxn],col[maxn],d[maxn][30],ans = 0; vector<int> hotel[55]; void input(){cin>>n>>k>>p;for(int i = 0;i < n;i++){scanf("%d%d",&col[i],&money[i]);hotel[col[i]].push_back(i);} } void init_rmq(){for(int i = 0;i < n;i++) d[i][0] = money[i];for(int j = 1;(1<<j) <= n;j++){for(int i = 0;i + (1<<j) - 1 < n;i++){d[i][j] = min(d[i][j-1],d[i+(1<<(j-1))][j-1]);}} } int rmq(int l,int r){int k = 0;while((1<<(k+1)) <= r-l+1) k++;return min(d[l][k],d[r-(1<<k)+1][k]); } void work(){int now;for(int i = 0;i < k;i++){if(hotel[i].size() < 2) continue;for(int j = 0;j < hotel[i].size() - 1;j++){for(int k = j + 1;k < hotel[i].size();k++){now = rmq(hotel[i][j],hotel[i][k]);if(now<=p) {ans += hotel[i].size() - k;break;}}}}cout<<ans<<endl; } int main(){input();init_rmq();work();return 0; }#include <iostream>#include <cstdio>using namespace std;int n,k,p,sum[201000][60],colour[201000],f[201000],ans;//f[]記錄距每個點最近的花費小于p的點，sum[i][j]存從0到i第j種顏色有幾個（前綴和）int main(){scanf("%d%d%d",&n,&k,&p);for(int i=1;i<=n;i++){int x;scanf("%d%d",&colour[i],&x);for(int j=0;j<k;j++)sum[i][j]+=sum[i-1][j];sum[i][colour[i]]++;if(x<=p)f[i]=i;elsef[i]=f[i-1];}for(int i=2;i<=n;i++){if(f[i]==i)ans+=sum[i][colour[i]]-1;//若其本身便是離其最近的花費小于p的點，那么前面榆次店一樣顏色的點都可與之組合，符合題目要求，所以加上前綴和，但因為會多加一個（該點自己，因兩兩組合），所以要減去一個elseans+=sum[f[i]][colour[i]];//若本身不是離其最近的花費小于p的點，那么離它最近的那個點向前與現在n所在這個點顏色相同的（包含n所在這個個點）點都可與之形成符合題目要求的組合，所以加上前綴和（從f[]往前的區間) }printf("%d",ans);return 0;}

?

轉載于:https://www.cnblogs.com/hyfer/p/5848268.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。