今天只写到D题，但是我还是来写题解了~
A和B感觉没什么好写的，略了。
C
题意
给你N个格子，进行Q次操作
1.在第x个格子里面加1，如果每个格子都大于1，每个格子都需要减去1
2.查询有几个格子大于x
思路
刚开始想着直接暴力，但是一看范围，嗯100%超时
每次所有格子大于1的时候都减掉1，如果暴力遍历所有格子好麻烦，那么！我们干脆不要减了，记录下需要减的次数cnt
在查询x的时候，因为我们没有给每个格子减cnt，所以我们需要给x加上tar是我们最后得出需要查询的值$tar=cnt+x$
解决了减掉1的麻烦，还有什么麻烦呢？有没有感觉查询大于tar如果每次都遍历一次好麻烦，那么！如何快速的找到几个格子大于tar呢？我们直接开一个数组S[i]来记录累计次数>=i 的单元格数量，现在我们查询只要输出S[tar]即可
好了，问题又来了，我们如何看是否需要cnt++(所有格子减1)，其实思考完上面，这个解决非常简单，只有当所有单元格的次数都大于cnt*的时候，我们才要减掉1，我们已经记录了次数数组S，所以只要$S[cnt+1]==n$ 我们就需要cnt++
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| void solve()
{
int n,q;
cin>>n>>q;
vector<int> a(n+1,0);
vector<int> S(q+5,0);
S[0]=n;
int cnt=0;
int qq=q;
while(q--)
{
int op,x;
cin>>op>>x;
if (op==1)
{
int c=a[x];
S[c+1]++;
a[x]++;
if (S[cnt+1]==n)
{
cnt++;
}
}
else if (op==2)
{
int tar=cnt+x;
if(tar>qq)
{
cout<<"0\n";
}
else {
cout<<S[tar]<<"\n";
}
}
}
}
|
D
题意
给你字符串S，问能不能重新排列 S ，让相邻的两个字符都不相同
思路
找到S中出现最多的字母的个数maxc，l是S的长度，如果最多的字母的个数大于长度的一半+1即$maxc>(l+1)/2$，那么肯定不可以，直接输出No
如果可以，还需要输出排序后的S
那么现在我们需要构造S，其实只要交替的放字母就好了，这里我使用了优先队列（堆）来实现
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| void solve()
{
int n;
cin>>n;
while(n--)
{
string s;
cin>>s;
map<char,int> mp;
int l=s.size();
int maxc=0;
for(int i=0;i<l;++i)
{
mp[s[i]]++;
if(mp[s[i]]>maxc)
{
maxc=mp[s[i]];
}
}
if(maxc<=(l+1)/2)
{
cout<<"Yes\n";
priority_queue<pair<int, char> > pq;
for (int i=0;i<26;i++)
{
if(mp[i+'a'])
{
pq.push({mp[i+'a'],i+'a'});
}
}
string ans="";
pair<int,char> pre(-1,' ');
while(!pq.empty())
{
auto now=pq.top();
pq.pop();
ans+=now.second;
now.first--;
if(pre.first>0)
{
pq.push(pre);
}
pre=now;
}
cout<<ans<<'\n';
}
else cout<<"No\n";
}
}
|
