CF1303D Fill The Bag(贪心)

洛谷评测地址：https://www.luogu.com.cn/problem/CF1303D

解析：

看了几个题解，应该是有两种贪心：从大到小或从小到大。

先写一下从大到小的做法吧。

对a[]进行从小到大的排序。

从大往小遍历。

很容易想到，尽量把大的往背包里放，即a[i]<=n时，直接放进去即可。

如果a[i]>n，这个a[i]拆不拆取决于 i 之前所有物品的大小(sum-a[i])

如果sum-a[i]<n，那么前面的不够，所以a[i]要拆，可以先拆一次，然后分到ai和ai+1处，i再从i+1处开始遍历。

如果sum-a[i]>=n，那么继续遍历即可，ai舍掉。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 95;
ll a[maxn];
ll n,m;
ll pre[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        ll sum=0;
        pre[0]=0;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i];
            sum+=a[i];
            pre[i]=pre[i-1]+a[i];
        }
        if(sum<n)
        {
            cout<<"-1"<<endl;continue;
        }
        int cnt=0;
        sort(a+1,a+1+m);
        for(int i=m;i>=1;i--)
        {
            if(a[i]<=n)
            {
                n-=a[i];
                sum-=a[i];
            }
            else if(sum-a[i]<n)
            {
                a[i]/=2;
                a[i+1]=a[i];
                i+=2;
                cnt++;
            }
            else if(sum-a[i]==n)
            {
                break;
            }
            else
            {
                sum-=a[i];
            }
        }
        cout<<cnt<<endl;
    }
}