美团笔试题（2018.10.09）

逻辑题20个要快点做，然后30个选择考的东西比较多。
编程两个。

1. 优惠券
   有一个满x减的优惠券，一共n个商品，每个只能选择一次，求能使用优惠券的最小价格。就是求n个数选任意几个加起来最接近x且大于等于x的数。
   1<x<10000
   1<n<100,每个商品价格小于等于100。

思路：暴力枚举是2^100，但是由于数据范围的原因，可以处理出x+100以内所有可达（能凑出）的数，然后取最接近的。处理算法就是用一个数组arr[x+105]表示状态，arr[i]=1表示i可以被凑出来。然后枚举所有的商品的价格，然后对arr数组中状态为1的点进行下一次变化，然后枚举所有的结束之后就是所有可能凑出来的结果，取最接近的。复杂度O（xn）

#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;

const int maxn = 1e4+1005;

int n, x, in[maxn], arr[maxn], flag[maxn];
int main()
{
    //freopen("D:\\input.txt", "r", stdin);
    cin>>n>>x;
    for(int i=0; i<n; i++)
        scanf("%d", in+i);
    for(int i=0; i<n; i++){
        if(arr[in[i]] == 0)
            flag[in[i]] = 1;
        arr[in[i]] = 1;
        for(int j=0; j<maxn-in[i]; j++)
            if(arr[j]==1 && !flag[j]){
                if(arr[j+in[i]] == 0)
                    flag[j+in[i]] = 1;
                arr[j+in[i]] = 1;
            }
        memset(flag, 0, sizeof(flag));
    }

    for(int i=x; i<maxn; i++){
        if(arr[i] == 1){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

2. 判定树
   给定数的所有的节点度序列，然后判定是不是一个树。
   题解：根据树的性质，所有节点度之和 = 2*（节点数-1）

#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;

const int maxn = 1e5+5;

ll T, n, sum, t;
int main()
{
    //freopen("D:\\input.txt", "r", stdin);
    cin>>T;
    while(T--){
        cin>>n;
        sum = 0;
        for(int i=0; i<n; i++){
            scanf("%lld", &t);
            sum += t;
        }
        if(sum == 2*(n-1))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}