Eisen's Blog

© 2023. All rights reserved.

POJ 1014

May 04, 2012

linkedin搜索

这道题让我还挺自豪的,因为我自己独立的把它写出来了(虽然经历了 timeover wronganswer),而且后来搜索网上的一些解答,貌似和他们的想法都不是很像的样子。而且,通过的数据貌似还挺好 0ms

Problem: 1014		User: yisnesia
Memory: 720K		Time: 0MS
Language: G++		Result: Accepted

这让我挺欣慰的。看到网上很多人都说到了 dp 的方法,我这里好像没有用唉,我用的差不多就是基本的搜索算法,然后用到了一个比较省时的启发:从 6->1 逆序搜索,并且一次性取尽量多这个价值的大理石 (如果一次仅仅取一个会超时的哦)。

#include <iostream>
#include <cstdio>

/*
 * http://poj.org/problem?id=1014
 *
 * 这道题我把它认为是搜索题
 * 要搜索的内容是 两个大小一样的分组
 * 那么我只需要找到一个大小恰好为总和一半的分组就达到目的了
 *
 * @author: aisensiy(http://weibo.com/alistapart)
 */
using namespace std;

int marbles[6];

bool search(int cur, int half) {
    // 这里引入了贪婪的思想,要从大的开始找,并且一次取尽量多
    for(int i=5; i>=0; i--) {
        if(!marbles[i]) continue;
        // 尽量多就是满足 或者 取尽
        int num = (half-cur) / (i+1) > marbles[i] ? marbles[i] : (half-cur) / (i+1);
        if(num == 0) continue;
        marbles[i] -= num;
        if(cur + (i+1) * num == half) return true;
        else if(search(cur + (i+1) * num, half)) return true;
        marbles[i] += num;
    }
    return false;
}

int main() {
    int counter=1, sum=0;
    while(1) {
        for(int i=0; i<6; i++) {
            cin>>marbles[i];
            sum += (i+1) * marbles[i];
        }
        if(!sum) break;
        // 这里有一个小 trick,如果总和本来就是计数
        // 则一定不能分成一样的两堆
        if(sum % 2 != 0 || !search(0, sum/2)) {
            printf("Collection #%d:\n"
               "%s\n\n", counter, "Can't be divided.");
        } else {
            printf("Collection #%d:\n"
                   "%s\n\n", counter, "Can be divided.");
        }

        counter++;
        sum = 0;
    }
    return 0;
}