HBC210247Cinema题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

China's cinemas are reopening after being closed for six months to help slow the spread of the coronavirus. Apollo has a cinema which contains n rows of seats and there are m seats in each row. We'll represent the seat on the x-th row and the y-th column as a pair of numbers (x, y). According to the policy, people in cinemas need to keep social distance. So two people can not sit at two neighboring seats. Two seats (x_1, y_1) (x 1 ​ ,y 1 ​ ), (x_2, y_2) (x 2 ​ ,y 2 ​ ) are considered to be neighboring if they have a common edge, i.e |x_1-x_2| + |y_1-y_2| = 1 ∣x 1 ​ −x 2 ​ ∣+∣y 1 ​ −y 2 ​ ∣=1. People will come to the box office to buy tickets one by one, and they are allowed to choose seats themselves. People can choose any valid seats. A seat is valid if it is not chosen by others and not neighboring with others' seats. The cinema cashier will stop sell tickets if there are no valid seats. As the boss of the cinema, Apollo wants to know the minimum number of tickets that can be sold in the worst case. We can assume there are enough people to buy tickets (i.e. the cinema cashier will continue to sell tickets until there are no valid seats).

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC210247Cinema题解