[原创]codeforces 382B B. Number Busters [二分答案+数学]【思维】

2017-01-22 13:52:08 Tabris_ 阅读数：308

博客爬取于2020-06-14 22:42:00
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54668103

题目链接：http://codeforces.com/contest/382/problem/B

----------------------------------------------------------------------------------------------------.
B. Number Busters
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Arthur and Alexander are number busters. Today they’ve got a competition.

Arthur took a group of four integers a, b, w, x (0 ≤ b < w, 0 < x < w) and Alexander took integer с. Arthur and Alexander use distinct approaches to number bustings. Alexander is just a regular guy. Each second, he subtracts one from his number. In other words, he performs the assignment: c = c - 1. Arthur is a sophisticated guy. Each second Arthur performs a complex operation, described as follows: if b ≥ x, perform the assignment b = b - x, if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b).

You’ve got numbers a, b, w, x, c. Determine when Alexander gets ahead of Arthur if both guys start performing the operations at the same time. Assume that Alexander got ahead of Arthur if c ≤ a.

Input
The first line contains integers a, b, w, x, c (1 ≤ a ≤ 2·109, 1 ≤ w ≤ 1000, 0 ≤ b < w, 0 < x < w, 1 ≤ c ≤ 2·109).

Output
Print a single integer — the minimum time in seconds Alexander needs to get ahead of Arthur. You can prove that the described situation always occurs within the problem’s limits.

Examples
input
4 2 3 1 6
output
2
input
4 2 3 1 7
output
4
input
1 2 3 2 6
output
13
input
1 1 2 1 1
output
0

----------------------------------------------------------------------------------------------------.
题目大意:
就是两个人,一个人有4个数字a,b,w,xa,b,w,x,另一个人有1个数字cc,每一秒第二个人的数字减一c-- ，每一秒第一个人的数字变化如下，if(b>=x) b=b-x;else a--,b=w-(x-b);现在问你最少多长时间之后a<=c?

解题思路:
很明显的二分答案,但是对于check部分还是要推敲一下,
首先if(b>=x) b=b-x;else a--,b=w-(x-b);
可以改变成 if(b>=x) b=b-x;else a--,b=b-x+w;
显然就是 在b<0的时候将+w,与此同时a–，
那么在c减少n的时候a减少的数m就满足 b=b-nx+mw&&b>0,(m取最小值);

与此同时注意a,c可能小于0,所以二分答案的边界要大一点.

附本题代码
----------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# include <bits/stdc++.h>
using namespace std;
# define abs(x)  (((x)>0)?(x):-(x))
const int N = 500000+5;
typedef long long int LL;
/***************************************/
LL ta,tb,tw,tx,tc;
bool check(LL n){
    LL a=ta,b=tb,w=tw,x=tx,c=tc;
    c-=n;
    b-=x*n;
    LL num = abs(b/w);
    b+=num*w;
    if(b>=0);
    else num++;
    a-=num;
    if(c<=a) return true;
    else return false;
}

int main(){
    ios::sync_with_stdio(false);

    cin>>ta>>tb>>tw>>tx>>tc;

    LL l=0,r=2e14,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;

    }
    cout<<ans <<endl;

    return 0;
}