【2023湖南大学ACM新生赛】M. Min Volume Difference（最小容积差）

????????题目大意是给出两个数字n, k。n代表总时长，k代表单位流量，在时刻 i (1 <= i <= n)?流量为k*i，那么将所有时刻的水的容积分成两组，求这两组水的容积之差的最小值。

????????本题的重点主要在数学分析，即运用数学归纳法构造贪心算法解题。比如在纸上写下1,2,3,4,5,6,7这几个数字，代表从时刻1到7的流量，那么容易发现，将七个数从后往前两两分组，那么一共可以分成三组：{7，6}，{5，4}，{3，2}，还剩下一个1。如果让组1取7,5,2;组2取6,4,3,1，那么此时两组和均为14，差为0；推广到所有分成m组（m为奇数），即 k % 4?= 3 的情况，都可以按照相应的分法使得分出的两组水的容积相等。

? ? ? ? 类似地，对于能两两分成偶数个组的情况（即 k % 4 = 0）,也可以分出两组相等容积的水。

? ? ? ? 进一步分析，对于能两两分成奇数个组的情况（k % 4 = 2）,例如1,2,3,4,5,6这几个数字可以分成以下三组：{6，5}，{4，3}，{2，1}。此时无论怎样分配都无法使得两组水容积相等，而最多只能分成容积相差1的两组，（严谨证明：这种情况数字和(所有水的容积)为奇数，而一个奇数只能被分成奇数和偶数相加，而奇数和偶数至少相差1），因此这种情况下输出水管的单位流量n。

? ? ? ? 类似地，对于能两两分成偶数个组并且余下一个的情况（k % 4 = 1），也最多只能分成两个容积相差1的两组，证明与上面类似，不再赘述。

? ? ? ? 综上，当 k % 4 = 0 或?k % 4 = 3时，输出0； k % 4 = 1 或 k % 4 = 2时，输出单位流量n。

完整代码如下：

#include <stdio.h>

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\input.txt", "r", stdin);
    long long n, k;
    scanf("%lld", &n);
    scanf("%lld", &k);
    if(n % 4 == 0 || n % 4 == 3)
        printf("%d", 0);
    else if(n % 4 == 1 || n % 4 == 2)
        printf("%lld", k);
    return 0;
}

?