F 同一字符的字典序怎么看?

想了一个小时,硬是没想出来,心态崩了 qwq

我的 F 的代码如下:

#include <bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

const int N = 1e6 + 10;

char s[N]; map<char, int> cnt; int n, k, pos;

void solve() {
	cnt.clear();
	cin >> n >> k >> s+1;
	pos = 0;
	for(int i = 1; i <= n; i++) cnt[s[i]]++;
	for(auto x : cnt) {
		if(k > x.second) k -= x.second;
		else {
			priority_queue<pair<int, int>> q;
			int lst = 0;
			L(j, 1, n)
			  if(s[j] == x.first) {
			  	if(lst) {
			  		q.push({-s[lst+1], lst});
				  }
				lst = j;
			  }
			q.push({-x.first, lst});
			while(--k)
			  q.pop();
			pos = q.top().second;
			break;
		}
	}
	cout << s[pos];
	for(int i = 1; i <= n; i++)
	  if(i ^ pos) cout << s[i];
	cout << '\n';
}

int main() {
//	freopen("f.in", "r", stdin);
//	freopen("f.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	int T; cin >> T;
	while(T--)
	  solve();
	return 0;
}



全部评论
取决于其原位置之后的字符
点赞 回复 分享
发布于 11-03 21:05 浙江
Hack样例: ``` 1 4 4 ccbc ``` 你的输出:ccbc 答案:cccb 另外,你的cin>>s+1我看牛客会编译错误,请问你是用了哪种语言提交的@AK_heaven
点赞 回复 分享
发布于 11-03 21:24 广东

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务