这道题有问题啊。。。

题目背景 有一些物品和一个小偷。 题目描述 有 NN 件物品，每件物品有质量 $M_i$ 和价值 $V_i$。 面条老师 有 K 个袋子，每袋可容纳的最大质量为 $C_i$。 每袋仅能放一个物品，问最多可以带走多少价值的物品？

？？？？？

给lxm595977369巨佬的代码改装了一下：（抄袭紫衫自删）

#include<bits/stdc++.h>
using namespace std;
struct T
{
    int m, p;
};
int n, k;
T a[300005];
int bag[300005];
long long ans;
priority_queue<int, vector<int>, less<int> > q;
bool cmp(T t1, T t2)
{
    if (t1.m == t2.m) return t1.p < t2.p ;
    else return t1.m < t2.m ;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].m, &a[i].p);
    for (int i = 1; i <= k; i++)
        scanf("%d", &bag[i]);
    sort(bag + 1, bag + k + 1);
    sort(a + 1, a + n + 1, cmp);
    int j = 1;
    for (int i = 1 ; i <= k; i++)
    {
        while (a[j].m <= bag[i] && j <= n)
        {
            q.push(a[j].p);
            j++;
        }
        if (!q.empty())
        {
            ans += q.top();
            q.pop();
        }
    }
    printf("%lld\n", ans);
    return 0;
}

9个RTE全是我的(汗)

原因就是没想起来如果队列无元素时候如果调用top() 和 pop() 会内存错误

所以这题属于完全靠我自己力量做出来的好耶可以不用写读后感了

属于贪心的算法(踌躇是否为01背包好久以后发现这个和01背包没有半毛钱关系)

我们可以先定义结构体储存每个物品的质量和价值然后从质量的从小到大排序，如果质量相等就价格从小到大排序
然后再定义一个数组储存每个袋子的装入最大质量，然后也是从小到大排序

结构体定义

struct T
{
    int m , p ;
};

物品排序规则

bool cmp( T t1 , T t2 )
{
    if( t1. m == t2.m )
    {
        return t1.p < t2.p ;
    }
    else return t1.m < t2.m ;
}

然后本题重点:优先队列和指针

定义优先队列储存小于等于bag[ i ]的所有物品价值
指针在循环中会用到，为了用来防止超时

定义优先队列priority_queue< int , vector< int > , less< int > > q ;

指针用来存储已经入队的物品在第几个

因为我们已经对每个袋子的最大容纳质量从小到大排过序了，所以之前入队的所有物品价值现在处理的袋子一定还是可以用的，因为加入到队列中的物品的质量一定小于等于之前的袋子最大容纳质量，而现在处理的袋子最大容纳质量一定大于等于之前处理袋子的最大容纳质量，所以现在处理袋子的最大容纳质量一定大于等于之前加入到队列中的物品质量
每次把小于等于袋子最大容纳质量物品价值加入优先队列，因为上一行的分析就可以得出现在入队的所有物品价值以后一定还是可用的
所以就可以在加入完以后直接调取队头来加入到最终答案中

也许我叙述的你可能听不明白，那么直接上这部分代码

int j = 1 ;//指针妙用
for( int i = 1 ; i <= k ; i ++ )
{
    while( a[ j ].m <= bag[ i ] and j <= n )
    {
        q.push( a[ j ].p ) ;
        j ++ ;
    }
    if( !q.empty() )//就没想到这行9次RTE啊啊啊
    {
        ans += q.top() ;
        q.pop() ;
    }

}

没有其他点了，代码奉上

#include<bits/stdc++.h>
using namespace std;
struct T
{
    int m , p ;
};
int n , k ;
T a[ 300001 ] ;
int bag[ 300001 ] ;
long long ans ;
priority_queue< int , vector< int > , less< int > > q ;
bool cmp( T t1 , T t2 )
{
    if( t1. m == t2.m )
    {
        return t1.p < t2.p ;
    }
    else return t1.m < t2.m ;
}
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n >> k ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        int t1 , t2 ;
        cin >> t1 >> t2 ;
        a[ i ].m = t1 , a[ i ].p = t2 ;
    }
    for( int i = 1 ; i <= k ; i ++ )
    {
        cin >> bag[ i ] ;
    }
    sort( bag + 1 , bag + k + 1 ) ;//前面的bag+1别写成bag了
    sort( a + 1 , a + n + 1 , cmp ) ;//这个同理
    int j = 1 ;//我是一枚可爱的指针(bushi
    for( int i = 1 ; i <= k ; i ++ )
    {
        while( a[ j ].m <= bag[ i ] and j <= n )
        {
            q.push( a[ j ].p ) ;
            j ++ ;
        }
        if( !q.empty() )//别学我没写这行9次RTE
        {
            ans += q.top() ;
            q.pop() ;
        }
    }
    cout << ans ;
    return 0 ;
}

贪心裸题 策略 将每个背包从小到大排序，每个物品以体积排序 对于从小到大的每一个背包 都要找到体积小于等于当前背包的价值最大值 讲所有小于等于当前背包体积的物品加入队列 用单调队列维护当前物品中的最大价值

#include <bits/stdc++.h>
using namespace std;
long long n,k,now=1,ans,c[300001];
struct Things{
	long long m,v;
}a[300001];
struct cmp1{
	bool operator()(Things a,Things b){
	    return a.v < b.v;
    }
};
priority_queue<Things,vector<Things>,cmp1>pq;
bool cmp(Things x,Things y){
	return x.m<y.m;
}
int main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i].m,&a[i].v);
	for(int i=1;i<=k;i++)
		scanf("%lld",&c[i]);
	sort(a+1,a+1+n,cmp);
	sort(c+1,c+1+k);
	for(int i=1;i<=k;i++){
		while(a[now].m<=c[i]&&now<=n)
			pq.push(a[now]),now++;
		if(pq.empty()) continue; 
		Things tmp=pq.top();pq.pop();
		ans+=tmp.v;
	}
	printf("%lld",ans);
	return 0;
}