顺序结构习题-1042纸牌问题题解

原题链接：https://ac.nowcoder.com/acm/contest/18839/1042

题目描述

小w想和你van纸牌
小w有两张纸牌，两张纸牌上都有相同的正整数n
每一轮一张纸牌上的数都可以减去小于等于另外一张纸牌上的数的数
每一轮只能操作和上轮不同的纸牌
小w想知道三轮之后两纸牌上数字之和的最小值
注意，不能减为负数

输入描述:

第一行1个正整数n。

输出描述:

一行一个整数
表示三轮之后两纸牌上数字和的最小值

示例1

输入

2

输出

1

数学题+1，代码不难。
这些题目就像小学奥数题，特定方法可以轻松解题，但却很难严格证明方法的可行性
比如周长固定的矩形，正方形面积最小

本题就用到了对分最小的思想

简化题意：给定两个相等的整数，每轮交替减去<=对方的整数，求三轮后两数和的最小值
为了得到最小值，第三轮一定选择减去对方以得到最小
考虑到对分最小，前两轮两数应互相减去对方的一半使得对减后两数的和最小
你要问我为什么，我也不知道 用就完了呗
简单糙下代码，AC

这是我的代码

#include <stdio.h>

int main ()
{
    int n;
    scanf("%d",&n);
    int a=n,b=n;
    a-=b/2;
    b-=b-a;
    a-=b;
    printf("%d\n",a+b);
    return 0;
}

注意

没有什么值得注意的，代码部分很简单

还是简单证明一下对分最小吧

给定俩整数都为n,第一轮减x，第二轮减y，第三轮减去对方

两轮后减去对方得到y-x，当x=y时y-x得到最小为0
得到一级条件x=y后进一步消元

得到结果n-x，要使结果最小，x要取最大，然由第二轮可得条件x<=n-x，因此

x<=1/2 n

所以每轮相减的数最大只能取半值