hotel.cpp

/*
 * =====================================================================================
 *
 *       Filename:  hotel.cpp
 *
 *    Description:  hotel
 *
 *        Version:  1.0
 *        Created:  2012年09月26日 19時07分55秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define MAX_HOTEL 200003
#define MAX_COLOR 52

int n, color_num, p; 
int color[MAX_HOTEL]; 
int price[MAX_HOTEL]; 
int plan[MAX_HOTEL]; 
int color_group[MAX_COLOR][MAX_HOTEL]; 

int main() {
    FILE *fin = fopen("hotel.in", "r"); 
    FILE *fout = fopen("hotel.out", "w"); 
    int result = 0; 
    int tmp[2] = {-1, -1}; 
    fscanf(fin, "%d %d %d", &n, &color_num, &p); 
    memset(plan, 0, sizeof(plan)); 
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%d %d", &color[i], &price[i]); 
        color_group[color[i]][++color_group[color[i]][0]] = i; 
        if(i == 0) {
            if(price[i] <= p) {
                plan[i] = 1; 
            }
            continue; 
        }
        if(price[i] <= p) {
            plan[i] = plan[i-1] + 1; 
        }else{
            plan[i] = plan[i-1]; 
        }
    }
    for(int i = 0; i < color_num; i++) {
        // counting i color 
        for(int j = 1; j <= color_group[i][0]; j++ ) {
            if(color_group[i][j] < tmp[1]) {
                result = result + tmp[0]; 
                continue; 
            }else{
                tmp[0] = -1; 
                tmp[1] = -1; 
            }
            for(int k = j + 1; k <= color_group[i][0]; k++) {
                if(plan[color_group[i][k]] - plan[color_group[i][j]] > 0) {
                    result = result + (color_group[i][0] - k + 1); 
                    tmp[0] = color_group[i][0] - k + 1; 
                    tmp[1] = color_group[i][k]; 
                    break; 
                }else if(plan[color_group[i][k]] - plan[color_group[i][j]] == 0 && \
                         (price[color_group[i][j]] <= p || price[color_group[i][k]] <= p)) {
                    result = result + (color_group[i][0] - k + 1); 
                    tmp[0] = color_group[i][0] - k + 1; 
                    tmp[1] = color_group[i][k]; 
                    break;
                }
            }
        }
        tmp[0] = -1; 
        tmp[1] = -1; 
    }
    fprintf(fout, "%d\n", result); 
    return 0; 
}