問題描述

牛牛正在挑戰(zhàn)一款名為01翻轉(zhuǎn)的游戲。游戲初始有A個0,B個1，牛牛的目標就是把所有的值都變?yōu)?，每次操作牛牛可以任意選擇恰好K個數(shù)字，并將這K個數(shù)字的值進行翻轉(zhuǎn)(0變?yōu)?，1變?yōu)?)。牛牛如果使用最少的操作次數(shù)完成這個游戲就可以獲得獎品，牛牛想知道最少的操作次數(shù)是多少？
例如:A = 4 B = 0 K = 3
0000 -> 1110 -> 1001 -> 0100 -> 1111
需要的最少操作次數(shù)為4

輸入描述

輸入為一行：
一共三個整數(shù)A(0 ≤ A ≤ 100,000),B(0 ≤ B ≤ 100,000),K(1 ≤ K ≤100,000).以空格分隔

輸出描述

輸出一個整數(shù)，表示最少需要的操作次數(shù)。如果不能完成，則輸出-1

輸入例子

4 0 3

輸出例子

4

分析

總的思路是：先把能翻的1都翻過來，每次翻K個，統(tǒng)計翻了多少次以及還剩下多少個1。剩下的1最多每翻兩次減少2*（總數(shù)字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;
}