[Codeforces1015D] Walking Between Houses (构造)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1015/problem/D

有$1~n$个房子，一个人从$1$出发，每次可以走任意步，现在希望走$k$次，求一个方案，这$k$次能走够$s$步（走到一个房子的地方，下一次再走的时候要以那个地方为起点）。

提供两种构造方法：

1：首先尽可能多地走$n-1$步，然后再走$s-(k-1)$步，最后剩下的都走$1$步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const LL maxn = 100100;
LL n, k, s;

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%lld%lld%lld",&n,&k,&s)) {
    LL tot = (n - 1) * k;
    if(tot < s) {
      printf("NO\n");
      continue;
    }
    if(k > s) {
      printf("NO\n");
      continue;
    }
    LL cur = 1;
    vector<LL> ret;
    while(k) {
      LL t = min(n - 1, s - (k - 1));
      cur = cur - t > 0 ? cur - t : cur + t;
      s -= t;
      k--;
      ret.push_back(cur);
    }
    printf("YES\n");
    for(int i = 0; i < ret.size(); i++) {
      printf("%lld%c", ret[i], " \n"[i==ret.size()-1]);
    }
  }
  return 0;
}

2：$p=\frac{s}{k}$，$q=s%k$，走$q$个$p+1$步，$k-q$个$p$步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
LL n, k, s;

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%lld%lld%lld",&n,&k,&s)) {
    LL tot = (n - 1) * k;
    if(tot < s) {
      printf("NO\n");
      continue;
    }
    if(k > s) {
      printf("NO\n");
      continue;
    }
    LL p = s / k;
    LL q = s % k;
    vector<LL> ret;
    LL cur = 1;
    for(int i = 0; i < q; i++) {
      ret.push_back((i % 2 == 0) ? p+2 : 1);
      cur = (i % 2 == 0) ? p+2 : 1;
    }
    if(cur == 1) {
      for(int i = 0; i < k - q; i++) {
        cur += (i % 2 == 0) ? p : -p;
        ret.push_back(cur);
      }
    }
    else {
      for(int i = 0; i < k - q; i++) {
        cur += (i % 2 == 0) ? -p : p;
        ret.push_back(cur);
      }
    }
    printf("YES\n");
    for(int i = 0; i < ret.size(); i++) {
      printf("%lld%c", ret[i], " \n"[i==ret.size()-1]);
    }
  }
  return 0;
}