E-缺席的神官——
本题的一个思路:先找出高级祭司第一点名和最后一次点名之间允许祭司不上班的间隙数,其实间隙数就是祭司的工作次数-1,就是k-1.而祭司的工作天数就是总天数-高级祭司第一次点名前-高级祭司最后一次点名后-最多的间隔天数。
附上代码:
#include <iostream> #include <algorithm> using namespace std; int main() { int n, m, k, a[2010], b[2010], sub = 0, ans; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n - 1; i++) { b[i] = a[i + 1] - a[i] - 1;//把每个间隙的天数写入数组 } sort(b + 1, b + 1 + n - 1);//给每个间隙按天数升序排列 for (int i = n - 1; i > n - 1 - (k - 1); i--) { sub += b[i];//把每个允许祭司不上班的间隙的天数相加 } ans = a[n] - a[1] + 1 - sub;//注意高级祭司第一点名前的天数和最后一次点名后的天数 cout << ans; return 0; }