如果和小于K#xff0c;则从小到大排序#xff0c;同时验证是否符合要求。

#pragma

这道题不难发现如果数字最终的和大于等于K我们可以把这个原数列从大到小排序得到最终答案。

#pragma

xr(xr3)(xr1)(cr^48),crgetchar();

return

chrono::high_resolution_clock::now().time_since_epoch().count();

struct

i1;in;i){suma[i];}if(sumk){coutYes\n;sort(a1,a1n,[](int

x,int

;}}else{coutNo\n;}}else{coutYes\n;sort(a1,a1n);for(int

i1;in;i){couta[i]

main(){ios::sync_with_stdio(false);

//int128不能用快读cin.tie();cout.tie();int

_yq;_yq1;//

cin_yq;while(_yq--){icealsoheat();}

//⠀⠀⠀

这题可以用dp的思想去求通过题目的数据我们可以大胆去猜首先复杂度一定要带个n其次m仅仅等于10也让我们可以发散性的去想到状压的

2^{10}

210的复杂度还可以再添一个m所以最终的复杂度最多为O(nmlog

2^{10}

我们可通过状压来枚举各个数是否符合条件可以放入的情况。

比如第i位假如我向这个数位放入的数字是j首先放入j的前提条件是在当前位数和上一个放入j的位数之间我们放入了至少一个a[j]此时j可以放入同时放入了j后j会使得后面所有a[x]j的数字都可以放入我们可以通过状态去枚举各个数字是否可以放入能放入的话对应的二进制位数就是1不能放入就是0。

#pragma

xr(xr3)(xr1)(cr^48),crgetchar();

return

chrono::high_resolution_clock::now().time_since_epoch().count();

struct

i0;in;i)dp[0][1i]1;dp[0][(1n)-1]1;for(int

i1;im;i){for(int

xo;x-(1(j-1));x|id[j];dp[i][x]dp[i-1][o];}}}}modint

ans0;for(int

i0;i(1n);i)ansdp[m][i];coutans;}

signed

main(){ios::sync_with_stdio(false);

//int128不能用快读cin.tie();cout.tie();int

_yq;_yq1;//

cin_yq;while(_yq--){icealsoheat();}

//⠀⠀⠀

还是我太菜了看题目都费劲最后还是不争气的看了题解竟然题解把查询放入了排序的cmp函数中确实还是我自己的思维太局限了容易想到的是我们把所有的数从小到大排序然后头尾相加再把相加的数通过二分按顺序放入这个数中重复上述操作知道符合最后条件为止O(nlogn)的复杂度所以不会超过25000次询问。

#pragma

xr(xr3)(xr1)(cr^48),crgetchar();

return

chrono::high_resolution_clock::now().time_since_epoch().count();

struct

icealsoheat(){cinn;vectorintve;for(int

i1;in;i){ve.push_back(i);}sort(ve.begin(),ve.end(),cmp);while(ve.size()1){int

leve[0];int

x;cinx;ve.erase(ve.begin());ve.pop_back();//

l0,rve.size()-1;int

mid;while(lr){mid(lr)1;if(cmp(x,ve[mid]))rmid;else

lmid1;}if(!cmp(x,ve[l]))l;ve.insert(ve.begin()l,x);}cout!endl;

signed

main(){ios::sync_with_stdio(false);

//int128不能用快读cin.tie();cout.tie();int

_yq;_yq1;//

cin_yq;while(_yq--){icealsoheat();}

//⠀⠀⠀