手机网站建设优势,各种中药材初加工平台,表白网址生成器,中国建设银行个人查询2817. 限制条件下元素之间的最小绝对差
可能别人有更好的解法#xff0c;我这写法是不断往线段树中插入数值#xff0c;每次先插入nums[i-x]#xff0c;然后搜索#xff08;1到i)中的最大值和(i到max)中的最小值去更新ans。
class Solution {
public:struct node{int mx,…2817. 限制条件下元素之间的最小绝对差
可能别人有更好的解法我这写法是不断往线段树中插入数值每次先插入nums[i-x]然后搜索1到i)中的最大值和(i到max)中的最小值去更新ans。
class Solution {
public:struct node{int mx,mn;int lson,rson;};int cnt 1;void insert(int pos,int l,int r,int d,vectornodetree){tree[pos].mx max(tree[pos].mx,d);tree[pos].mn min(tree[pos].mn,d);if(lr)return;int mid (lr)1;if(dmid){if(tree[pos].lson0){tree[pos].lson cnt;tree[cnt-1].mn (130);}insert(tree[pos].lson,l,mid,d,tree);}else{if(tree[pos].rson0){tree[pos].rson cnt;tree[cnt-1].mn (130);}insert(tree[pos].rson,mid1,r,d,tree);}}int getmx(int pos,int l,int r,int L,int R,vectornodetree){if(Ll rR)return tree[pos].mx;int mid (lr)1;int mx 0;if(Lmid tree[pos].lson)mx getmx(tree[pos].lson,l,mid,L,R,tree);if(midR tree[pos].rson)mx max(mx,getmx(tree[pos].rson,mid1,r,L,R,tree));return mx;}int getmn(int pos,int l,int r,int L,int R,vectornodetree){if(Ll rR)return tree[pos].mn;int mid (lr)1;int mx (130);if(Lmid tree[pos].lson)mx getmn(tree[pos].lson,l,mid,L,R,tree);if(midR tree[pos].rson)mx min(mx,getmn(tree[pos].rson,mid1,r,L,R,tree));return mx;}int minAbsoluteDifference(vectorint nums, int x) {int tnx0;for(auto i:nums)tnx max(tnx,i);vectornodetree(nums.size()5);int ans (130);tree[0].mn (130);for(int i0;inums.size();i){if(i-x0)insert(0,1,tnx,nums[i-x],tree);int d getmx(0,1,tnx,1,nums[i],tree);if(d)ans min(ans,nums[i]-d);d getmn(0,1,tnx,nums[i],tnx,tree);if(d!(130))ans min(ans,d-nums[i]);}return ans;}
};看了看别人题解直接用set写是真的牛。自己还是见识短浅了。
2813. 子序列最大优雅度
暴力乱搞考虑两种极端情况一种无脑选profit大的一种优先选不同类型的。 我们先选不同类型的记录值然后选profit大的没选过的 更新一下值然后选完后就会变成profit前k个的情况。取最大值就行。
class Solution {
public:bool flag[100010];long long findMaximumElegance(vectorvectorint items, int k) {sort(items.begin(),items.end(),[](vectorinta,vectorintb){return a[0]b[0];});mapint,intmp;auto cmp [](pairint,int a,pairint,int b){return a.firstb.first;};priority_queuepairint,int ,vectorpairint,int, decltype(cmp)que(cmp);long a0,b0;int cnt 0;long long tp 0,dc 0;long long ans 0;vectorboolflag(items.size());int num 0;for(int i0;iitems.size();i){if(dck){if(!mp[items[i][1]]){que.push({items[i][0],items[i][1]});mp[items[i][1]] 1;dc;flag[i] 1;tpitems[i][0];ans max(ans,tpdc*dc);num;}}elsebreak;}for(int i0;ik;i){if(numk flag[i] 0){tp items[i][0];num;}else if(!que.empty() flag[i] 0){auto [a,b] que.top();tp- a-items[i][0];dc--;que.pop();}ans max(ans,tpdc*dc);}return ans;}
};2812. 找出最安全路径
先通过一遍bfs计算出每一个点的安全系数 然后从00开始跑bfs每次选择安全系数最大的点并记录每条路径中最小的安全系数。
class Solution {
public:struct node{int x,y,val;bool operator(const node a)const{return vala.val;}};int maximumSafenessFactor(vectorvectorint grid) {int n grid.size();int m grid[0].size();vector dis(n,vectorint(m,(130)));queuepairint,intq;for(int i0;in;i)for(int j0;jm;j)if(grid[i][j]){dis[i][j] 0;q.push({i,j});}int f[] {0,-1,0,1,1,0,-1,0};while(!q.empty()){auto [x,y] q.front();q.pop();for(int i0;i4;i){int nx xf[i1];int ny yf[i1|1];if(nx0 nxn ny0 nym){if(dis[nx][ny]dis[x][y]1){dis[nx][ny] dis[x][y]1;q.push({nx,ny});}}}}vector cost(n,vectorint(m,0));vector flag(n,vectorbool(m,0));priority_queuenodeque;que.push({0,0,dis[0][0]});cost[0][0] dis[0][0];while(!que.empty()){auto u que.top();que.pop();if(flag[u.x][u.y])continue;flag[u.x][u.y] 1;for(int i0;i4;i){int nx u.xf[i1];int ny u.yf[i1|1];if(nx0 nxn ny0 nym){if(cost[nx][ny]cost[u.x][u.y] !flag[nx][ny]){cost[nx][ny] min(cost[u.x][u.y],dis[nx][ny]);que.push({nx,ny,dis[nx][ny]});}}}}return cost[n-1][n-1];}
};2818. 操作使得分最大
统计每一个数字的最大区间 [ L , R ] [L,R] [L,R]满足当 L l i 且 i r R Lli 且 irR Lli且irR时该区间的分数为 n u m s [ i ] nums[i] nums[i],这个区间使用单调栈统计然后每个 n u m [ i ] num[i] num[i]可以被使用次数就为 ( i − L 1 ) ∗ ( R − i 1 ) (i-L1)*(R-i1) (i−L1)∗(R−i1)。最后把数字从大到小排序然后选择k个即可。
class Solution {
public:const int mod 1e97;int maximumScore(vectorint nums, int k) {vectorint score(nums.size());auto calscore [](int a){int ret 0;for(int i2;i*ia;i){if(a%i0){ret;while(a%i0)a/i;}}if(a!1)ret;return ret;} ;for(int i0;inums.size();i)score[i] calscore(nums[i]);vectorintpre(nums.size());vectorintsa(nums.size(),nums.size());stackintddz;for(int i0;inums.size();i){while(!ddz.empty() score[i]score[ddz.top()]){sa[ddz.top()] i;ddz.pop();}if(ddz.empty())pre[i] -1;else pre[i] ddz.top();ddz.push(i);}auto cmp [](pairint,long longa,pairint,long longb){if(a.firstb.first)return a.secondb.second;return a.firstb.first;};priority_queue pairint,long long, vectorpairint,long long , decltype(cmp) que(cmp);for(int i0;inums.size();i){que.push({nums[i],(sa[i]-i)*(i-pre[i])});}long long ans 1;auto qpow [](long long a,long long b)-long long{long long ret 1;while(b){if(b1) ret (a*ret)%mod;a a*a%mod;b1;}return ret;};while(k){auto [x,y] que.top();que.pop();ans ans*qpow(x,min(y,1ll*k))%mod;k - min(y,1ll*k);}return ans;}
};
