H.奇怪的背包问题增加了

柔光的暖阳◎ 2023-07-18 09:15 1阅读 0赞

[H.奇怪的背包问题增加了][H.]

题意：  
有一个2 ^ 30体积的背包，有m个物品，每个物品的体积都是2的指数次幂。问能不能恰好把背包装满，并输出选择的结果用字符串表示。

题解：  
我们累加所有物品体积，看是不是比背包体积大。  
如果小于背包体积肯定不满足题目要求；  
如果大于背包体积肯定可以恰好装满背包，我们只需要把物品体积从大到小排序，依次判断就行了。

图片来自于：  
[Frozen\_Guardian][Frozen_Guardian]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70_pic_center]

code：

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    pair<ll,ll> p[maxn];
    ll vis[maxn];
    int main()
    { 
    	io();
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		ll mm=(1<<30),ans=0;
    		ll n;
    		cin>>n;
    		for(int i=1;i<=n;i++)
    		{ 
    			ll m;
    			cin>>m;
    			p[i].first=(1<<m);
    			p[i].second=i;
    			ans+=p[i].first;
    			vis[i]=0;
    		}
    		if(ans<mm)
    			cout<<"impossible"<<endl;
    		else
    		{ 
    			sort(p+1,p+n+1,greater<pair<ll,ll> >() ); 
    			for(int i=1;i<=n;i++)
    			{ 
    				mm-=p[i].first;
    				vis[p[i].second]=1;
    				if(mm==0) break;
    			}
    			for(int i=1;i<=n;i++)
    				cout<<vis[i];
    			cout<<endl;
    		}
    	}
    	return 0;
    }

[H.]: https://ac.nowcoder.com/acm/contest/4784/H
[Frozen_Guardian]: https://blog.csdn.net/qq_45458915/article/details/105020943
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/6d70b2e9758843e38d9cdb5baef76349.png