首页 > 其他 > 详细

暑期训练1 Gym-102623L Lottery Tickets 模拟 贪心构造

时间:2020-08-19 22:13:37      阅读:104      评论:0      收藏:0      [点我收藏+]

a[i] 表示可以选择数i的个数。

对于每一组询问a,求出能够组合出的被4整除的最大的数。

显然是贪心构造,被4整除就等价于末尾两位被4整除。

需要注意的点有: 前导0,单个数字

这里通过string自带的比较性质写了一个cmp函数。

void solve() {
    memset(val, 0, sizeof val);
    vector<string> v;
    for (int i = 0; i < 10; i++) {
        int x = readint();
        val[i] += x;
    }
    int sum = 0;
    for (int i = 1; i < 10; i++) sum += val[i];
    if (!sum) {
        puts("0");
        return;
    }
    int f1, f2;
    for (int i = 0; i < 100; i += 4) {
        if (i < 10) f1 = 0;
        else f1 = get1(i);
        f2 = get2(i);
        if (!f1 && val[f2]) {
            string xx;
            xx.push_back(f2 + 0);
            v.push_back(xx);
        }
        if (val[f1] && val[f2]) {
            val[f1]--;
            val[f2]--;
            if (f1 == f2 && val[f1] < 0) {
                val[f1]++;
                val[f2]++;
                continue;
            }
            string tmp;
            for (int i = 9; i >= 0; i--) for (int j = 0; j < val[i]; j++) tmp.push_back(i + 0);
            tmp.push_back(f1 + 0);
            tmp.push_back(f2 + 0);
            val[f1]++, val[f2]++;
            int head = 0;
            while (tmp[head] == 0) head++;
            tmp = tmp.substr(head);
            v.push_back(tmp);
        }
    }
    if (!v.empty()) {
        sort(v.begin(), v.end(), cmp);
        cout << v.back() << "\n";
        return;
    }
    puts("-1");
}

int main() {
    int T = readint();
    while (T--) solve();
}

 

暑期训练1 Gym-102623L Lottery Tickets 模拟 贪心构造

原文:https://www.cnblogs.com/hznumqf/p/13531495.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!