SEO案例网站建设公司/游戏推广一个月能拿多少钱

Loop

题意：
就是给你一个数组，然后你可以操作k次，每次可以选择两个数l和r，让va[l]插到va[r]的后面。然后问你操作k次后，这个数组的字典序最大是多少。

思考：
1.每次可以让一个数插到后面，然后让你求字典序最大，那么我肯定保证最前面的能多大就多大。所以第一个可以从[1,k+1]这段区间取一个最大值成为最前面的数，因为你可以把前面的k个都扔到后面。所以每次我就可以把某段区间的最大值当成前面的，这个最大值前面的数都扔到后面，扔到哪里先不管。
2.对于扔掉点我都放在一个序列里，然后就一直从前往后处理，直到处理到最后一个数。现在得到两个序列，一个是每次固定的最大值的序列，一个是我扔掉的数的序列。然后我就可以从前往后遍历最大值的序列，如果我扔掉的序列的数大于当前遍历的数，那么我就可以先放这个仍的数，因为每次我都往后仍嘛，我就让它扔在这。
3.但是当时我思考，会不会它不应该仍在这的呢？应该仍在靠前的地方，其实不会，因为第一次你去的是[1,k+1]的最大值，那么这个你仍的数肯定不会出现在前面。所以不用担心这个的。
4.对于每次你可以在[i,i+k-1]这段区间找最大值，如果每次暴力找超时了，我可以先用线段树维护出最大值。然后维护n个set，每个set是每个数字出现的位置。我就可以在s[maxn]找到第一个>=i的位置，为啥是第一个，因为我处理第一个就够了，剩下的k留给后面的。这样就找到了最大值的位置。牛客练习赛85-哲学家的沉思，这个题目也是用的这种操作。
5.对于输出答案的时候，如果固定序列的当前值>=扔掉序列的最大值，我是先输出谁呢？要先输出当前固定序列的值，因为扔掉的数最大值就那么大了，但是固定序列的最大值后面可能还会更大呢，所以这里是个细节。
6.还有一点就是，当k非常大的时候，如果都用不k，其实用管，我就选l==r操作后等于没有操作。如果r必须>l。那么就要判断答案数组里面是否有相邻的相同值，让他俩换，如果没有，我就换最后两个直到k为0。

代码：

 #include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define node_l node<<1
#define node_r node<<1|1using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e6+10,M = 2010;int T,n,m,k;
int va[N];
int vb[N];
int vc[N];
int cnt1,cnt2;
set<int > s[N];struct seg_max{struct node{int L,R;int maxn;}t[4*N];void pushup(int node){t[node].maxn = max(t[node_l].maxn,t[node_r].maxn);}void build(int node,int l,int r){t[node].L = l,t[node].R = r;t[node].maxn = -inf; //多次建树初始化细节，虽然会被pushup更新，但是有时候没有pushup的时候，就会错，所以就都初始化掉就可以了if(l==r){t[node].maxn = va[l];return ;}int mid = (l+r)>>1;build(node_l,l,mid);build(node_r,mid+1,r);pushup(node);}void update(int node,int l,int r,int value){if(t[node].L>=l&&t[node].R<=r){t[node].maxn = max(t[node].maxn,value);return ;}int mid = (t[node].L+t[node].R)>>1;if(r<=mid) update(node_l,l,r,value);else if(l>mid) update(node_r,l,r,value);else update(node_l,l,mid,value),update(node_r,mid+1,r,value);pushup(node);}int query(int node,int l,int r){if(t[node].L>=l&&t[node].R<=r) return t[node].maxn;int mid = (t[node].L+t[node].R)>>1;if(r<=mid) return query(node_l,l,r);else if(l>mid) return query(node_r,l,r);else return max(query(node_l,l,mid),query(node_r,mid+1,r));pushup(node);}
}t_max;void solve()
{cnt1 = 0,cnt2 = 0;for(int i=1;i<=n;i++){int l = i,r = min(n,i+m);int maxn = t_max.query(1,l,r); //这段区间的最大值int idx = *s[maxn].lower_bound(l); //第一个出现的位置vb[++cnt1] = va[idx];for(int j=i;j<idx;j++) vc[++cnt2] = va[j];m -= idx-i;i = idx;}sort(vc+1,vc+1+cnt2,greater<int>());vector<int > anw;int i = 1,j = 1;while(i<=cnt1||j<=cnt2){if(i>cnt1){anw.pb(vc[j++]);continue;}if(j>cnt2){anw.pb(vb[i++]);continue;}if(vb[i]>=vc[j]) anw.pb(vb[i++]); //还是先拿固定序列的else anw.pb(vc[j++]);}for(int i=0;i<anw.size();i++){cout<<anw[i];if(i!=anw.size()-1) cout<<" ";}cout<<"\n";
}signed main()
{IOS;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>va[i];t_max.build(1,1,n);for(int i=1;i<=t_max.query(1,1,n);i++) s[i].clear(); //初始化for(int i=1;i<=n;i++) s[va[i]].insert(i);solve();}return 0;
}

总结：
多多思考，注意细节。