【NOIP 2011 提高组 Day1】选择客栈

题目

---

题解

–要我说，这道题是非常之骚气的，首先有很多很多不同的方法，当然，我可是蒟蒻，所以说，我的方法不是最快的，时间复杂度O(nlogn)，最快的是O(n）的，虽然我不明白，但是没什么问题，可以过的
–然后是我方法的详解：
首先把相同颜色的旅馆，还有可以小聚的咖啡馆都用vector存下啦，假设如下图：
sc[0][ ]={1 , 2 , 4 , 6 , 7}
sc[1][ ]={3, 5}
star[ ]={1, 5 }
(sc[MAXN]是存相同颜色的旅馆，star存可以小聚的咖啡馆）
很明显：方案是（1,2）（1,4）（4,6）（1,6）（2,6）（1,7）（2,7）（4,7）（3,5）
（这个用于验证以下方法的正确性）

接着我们对每两个在sc中相邻的旅馆分析（比如：（1,2），（4,6）），有两种情况：
1. 他们之间可以小聚，那么选他们肯定是一种方案，然后发现，前面所有的同色旅馆都可以和他们中的后者组成可行方案，因为这个范围内肯定包含了那个用于小聚的旅馆（比如：（4,6）可行，那么（1,6）（2,6）都可行）
2. 他们之间不可以小聚，那么他们绝不能选，但是前面已经满足条件的同色旅馆的前者可以和他们组成可行方案，理由同上（比如：（2,4）不行，但是（1,4）可行）
注意：这里有一种巨坑的情况，让我一直wa掉的
虽然目前的这两个不行，而且前面两个也不行，但是他们中间有可行的，那他们也行（比如：（6,7）不行，（2,4）也不行，但是（2,7）可行）相当于前面的两个是可行的

现在我们只需要用a和b两个变量储存目前不可行和可行的旅馆组数，按照以上分析进行各种加，就能得到答案了

当然在查找目前打这两个是否可行的时，用一个lower_bound就会快很多

---

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=55;

int n,k,p;
int c,m;
vector<int>sc[MAXN];
vector<int>star;
long long ans;

int main(){
//  freopen("hotel.in","r",stdin);
//  freopen("hotel.out","w",stdout);
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&c,&m);
        sc[c].push_back(i);
        if(m<=p)
            star.push_back(i);  
    }
    for(int i=0;i<k;i++){
        long long a=0,b=0;
        for(int j=0;j<sc[i].size()-1;j++){
            int x=sc[i][j],y=sc[i][j+1];
            int z=lower_bound(star.begin(),star.end(),x)-star.begin();
            z=star[z];
            if(z<=y){
                b++;
                b=a+b;
                a=0;
                ans+=b;
            }
            else{
                a++;
                ans+=b;
            }
        }
    }
    cout<<ans;
    return 0;
}