对象存储调度问题

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7087

题目描述：

给定 n 个大小 A1,A2,⋯,An 为 2 的整数次幂的数据对象，以及 m 个剩余空间为 B1,B2,⋯,Bm 的分条。问是否可以通过对数据对象进行聚合，使得能用现有的 m 个分条把所有 n 个对象存下来。T 组数据。

Sample input：

3
4 2
2 2 4 8
4 12
4 2
2 2 4 8
3 13
4 2
1 2 4 8
5 10

Sample output：

Yes
No
Yes

思路：利用大根堆存储分条的剩余空间，然后每次用最大分条剩余空间去匹配最大的数据对象。重点在于数据对象的大小一定是2的整数次幂，这就保证了贪心的正确性，因为前面n-1个数是第n个数的组成部分，如果它们之和大于n，那么其中一部分也一定可以用n替换，所以不会浪费分条空间。

代码实现：

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
int a[N];
priority_queue<int> pq;
int n, m, T;

int main()
{
    scanf("%d", &T);
    while( T-- )
    {
        while(!pq.empty()) pq.pop();

        scanf("%d%d", &n, &m);
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        for(int i=0; i<m; i++)
        {
            int t;
            scanf("%d", &t);
            pq.push(t);
        }

        sort(a, a + n);

        int f = 0;
        for(int i=n-1; i>=0; i--)
        {
            int mx = pq.top(); pq.pop();
            if(mx >= a[i])
            {
                mx -= a[i];
                pq.push(mx);
            }
            else
            {
                puts("No");
                f = 1;
                break;
            }
        }
        if(!f) puts("Yes");
    }
    return 0;
}

参考文献：https://blog.csdn.net/qq_51354600/article/details/119851370