2015ACM-ICPC亚洲区域赛EC-Final M：November 11th

February 26, 2016

题目 PDF 下载

题意：R*S 的电影院座位图，B 个坏掉的座位。所有人的左右两侧不能有人，问整个影院最多坐多少人，最少坐多少人。

对每一行单独处理。

最大值是两个人隔着坐，如果有一段连续的区间长度是 L，那么最大值是 ceil(L/2)。

最小值是一个人可以占连续的三个位置，那么最小值就是 ceil(L/3)。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    for(int cas = 1; cas <= t; cas++){
        int r, s, rr, ss;
        scanf("%d%d", &r, &s);
        int pic[r][s];
        memset(pic, 0, sizeof(pic));
        int b;
        scanf("%d", &b);
        while(b--){
            scanf("%d%d", &rr, &ss);
            pic[rr][ss] = 1;
        }
        int cnt = 0, maxx = 0, minn = 0;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < s; j++){
                if(pic[i][j] == 0){
                    cnt++;
                }
                if(pic[i][j] != 0 || (pic[i][j] == 0 && j == s-1)){
                    maxx += ceil(1.0*cnt/2);
                    minn += ceil(1.0*cnt/3);
                    cnt = 0;
                }
            }
        }
        printf("Case #%d: %d %dn", cas, maxx, minn);
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]