01翻转

问题描述

牛牛正在挑战一款名为01翻转的游戏。游戏初始有A个0,B个1，牛牛的目标就是把所有的值都变为1，每次操作牛牛可以任意选择恰好K个数字，并将这K个数字的值进行翻转(0变为1，1变为0)。牛牛如果使用最少的操作次数完成这个游戏就可以获得奖品，牛牛想知道最少的操作次数是多少？
例如:A = 4 B = 0 K = 3
0000 -> 1110 -> 1001 -> 0100 -> 1111
需要的最少操作次数为4

输入描述

输入为一行：
一共三个整数A(0 ≤ A ≤ 100,000),B(0 ≤ B ≤ 100,000),K(1 ≤ K ≤100,000).以空格分隔

输出描述

输出一个整数，表示最少需要的操作次数。如果不能完成，则输出-1

输入例子

4 0 3

输出例子

4

分析

总的思路是：先把能翻的1都翻过来，每次翻K个，统计翻了多少次以及还剩下多少个1。剩下的1最多每翻两次减少2*（总数字S-K），再考虑一些特殊情况就好了。

note

暂时不能完全理解= =

代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int a, b, k;
    scanf("%d%d%d", &a, &b, &k);

    int s = a + b;
    int r = a % k;
    int c = a / k;

    if (a == 0 || r == 0);
    else if ((s <= k) || ((r & 1) && !(k & 1)))
        c = -1;
    else if (!((k + r) & 1) && c > 0 && b + k * c >= 2 * k - (k + r) / 2)
        c++;
    else if (!(r & 1))
        c += 2 * ceil((double)r / (2 * (s - k)));
    else
        c += 2 * ceil((double)(k - r) / (2 * (s - k))) + 1;

    printf("%d\n", c);

    return 0;
}