codeforces GYM 101431D(构造)

Problem D. Vera and Dogs

构造

GYM

题目链接

题目大意

有N个房子和N*X只狗。每个房子可以成为X只狗的第一选择和另外X只狗的第二选择。每只小狗都只有一个第一选择和一个第二选择。小狗优先选择第一选择的房子，如果房子满了，就选择第二选择。每个房子只能容纳X+1只小狗。每天晚上都会有一间房子不能使用。问，怎么分配小狗的第一选择和第二选择，使得无论哪间房子不能使用，都能保证所有小狗都有房间选择(输出任意一组解)。无解输出

-1

数据范围： 1≤N,X≤2017 X∗N≤2017

解答

如果 X≥N 则无解。

否则，对于第i个房子，可以让其成为X只狗的第一选择，然后这X只狗的第二选择分别选择编号为 i+1 , i+2 , … , i+X 房子即可(编号大于N的减N)。这样正好就可以分配完。

AC代码