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

2023-12-31 15:24:33

????????题目大意是给出两个数字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;
}

?

文章来源:https://blog.csdn.net/Andy_Xie007/article/details/135307818
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。