Memory

题目链接

题目大意：
称药片，N瓶药里面有两瓶不合格，每片比标准轻0.1g，称一次就得到是哪一瓶。因为题目是汉语的就不多说了。

思路：
感觉这道题有点像软协今年的那个面试题。。但是做法不一样，比如5瓶药12345,这样称就会出现1+4和2+3是一样的，没法判断，比赛的时候没想出来，现在也不知道这道题应该归到哪一类里面。。。

#include <iostream>
#include <string.h>
#include <set>
using namespace std;
int a[55];
set<int> ss;
bool check(int i, int t);

int main(){
    int n;
    cin >> n;
    memset(a, 0, sizeof(a));
    a[1] = 1;
    a[2] = 2;
    ss.insert(3);
    int t = 3;

    for(int i = 3; t <= n; i++){
        if(check(i, t)){
            a[t] = i;
            for(int j = 1; j < t; j++){
                ss.insert(a[j]+i);
            }
            ++t;
        }
    }

    if(n==2){
        printf("1 1");
    }
    else{
        printf("1");
        for(int i = 2; i <= n; i++){
            printf(" %d", a[i]);
        }
    }

    return 0;   
}

bool check(int i, int t){
    for(int j = 1; j < t; j++){
        if(ss.count(a[j]+i)){
            return false;
        }
    }
    return true;
}