UVALive 7464 Robots （贪心）

Robots

题目链接：

http://acm.hust.edu.cn/vjudge/contest/127401#problem/K

Description

http://7xjob4.com1.z0.glb.clouddn.com/168817810b54cfa4ffaebf73d3d1b0c5

Input

The input consists of multiple test cases. First line contains a single integer t indicating the number of test cases to follow. Each of the next t lines contains four integers — x, y, m, n.

Output

For each test case, output on a single line the minimum number of seconds to sum up all numbers from all robots.

Sample Input

1 1 10 1 2

Sample Output

11
##题意：有X和Y两类机器人各n m个，现在要将所有机器人上的信息传送到基点Base. 同一时刻每个机器人(包括Base)只能发给一个对象，也只能接受一个对象的信息. X类的机器人发送数据的时间是x，Y类的是y. (x < y). 求把所有信息传送到Base的最少时间.
##题解：直接按样例的思路来贪心即可. 首先，Y的发送时间大于X的发送时间. 把Y的信息先转存到X(在这同时选一个Y发送到BASE) 一定比把所有Y依次传送到BASE要好. 同一边的可以先两两合并再发送.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 300 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

int main(int argc, char const *argv[])
{
//IN;

int t; cin >> t;
while(t--)
{
    int x,y,m,n;
    cin >> x >> y >> m >> n;

    int ans = 0;
    while(n > m) {
        ans += y;
        n -= m + 1;
    }

    if(n) {
        ans += y;
        int last = m - n;
        int cur = 0;
        while(last > 0) {
            if(cur + x > y) break;
            cur += x;
            last /= 2;
        }
        m = last + n;
    }
    while(m > 0) {
        ans += x;
        m /= 2;
    }

    printf("%d
", ans);
}

return 0;

}