题意可知,要使打出的伤害最高,出的牌要最多
我们考虑牌数最多的牌,因为少的牌能用来当多的牌的挡板,是一定能用掉的
所以我们考虑 最多牌的次数为m ,剩下的牌为 n-m 那最多的牌次数最多可以有 n-m+2 个 因为最末尾可以连放两个
于是有两种情况
1.m<=n-m+2 全部牌都能打出
2.m>n-m+2 多的牌太多了 多出的牌为 m - (n-m+2) 减去即可
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
cin>>n;
vector<int> a(n);
int sum=0;
int m=0;
int t=0;
vector<int> cnt(1005,0);
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
cnt[a[i]]++;
if(cnt[a[i]]>m){
m=cnt[a[i]];
t=a[i];
}
}
if(m<=n-m+2){
cout<<sum<<'\n';
}
else cout<<sum- t * (2*m -n -2)<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ttt=1;
cin>>ttt;
while(ttt--){
solve();
}
return 0;
}
|
留下的字符串为交替,且我们删去的字符也是要交替的
设原来有 N个0 和 M个1 ,最终有 n个0 和 m个1
我们删去了d0 = N - n 个0 d1 = M-m 个 1 且 |d0 - d1| < = 1
代入得 | (N-M) - (n-m) | < =1
令 x = (N-M) y = (n-m) 且 y的值只能在 {-1,0,1} 三者取
因| x - y | <= 1 即 x>2 或 x<-2 无解
若有解 考虑最少操作次数,也就是保留的字符串要最长
理论最长肯定是 原先字符串 01块 的大小 我们可以算出这个 01 块 的 Y 值(即0和1的个数差)
因为 最终 y肯定在{-1,0,1} 三者取 我们遍历一遍
算出 Y 到 y 这个过程中要变的 长度即 min(|Y-y|) 保留的就是01块长度 len - |Y-y|
最后的操作次数就是原长减去保留
代码
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
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
cin>>n;
string s;
cin>>s;
int cnt0=0;
int cnt1=0;
for(int i=0;i<n;i++){
if(s[i]=='0') cnt0++;
else cnt1++;
}
int x=cnt0-cnt1;
if(x<-2 || x>2){
cout<<-1<<"\n";
return;
}
int k0=0;
int k1=0;
k0+=(s[0]=='0')?1:0;
k1+=(s[0]=='1')?1:0;
for(int i=1;i<n;i++){
if(s[i]!=s[i-1]){
k0+=(s[i]=='0')?1:0;
k1+=(s[i]=='1')?1:0;
}
}
int len=k0+k1;
int ans=n;
for(int y=-1;y<=1;y++){
if(abs(x-y)<=1){
int d=abs((k0-k1)-y);
ans=min(n-(len-d),ans);
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ttt=1;
cin>>ttt;
while(ttt--){
solve();
}
//solve();
return 0;
}
|
看题意依旧贪心
答案最大值:m 不管稳定值 一层直接移除完
接下来就贪 有没有更小的可能 也就是小于m 但把某一层的稳定值变为0 或更低了
注意到下层的能影响上层的 那我们从最下层开始遍历 记录 减少的稳定值 跟 本层稳定值比较 更新ans即可
代码
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
50
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n,m;
cin>>n>>m;
vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
vector<vector<ll>> a(n,vector<ll>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
ll ans=m;
ll total=0;
priority_queue<ll,vector<ll>,greater<ll>> pq;
for(int i=n-1;i>=0;i--){
for(int j=0;j<m;j++){
pq.push(a[i][j]);
total+=a[i][j];
}
while(pq.size()>ans){
total-=pq.top();
pq.pop();
}
while(pq.size()>0 && total-pq.top()>=v[i]){
total-=pq.top();
pq.pop();
}
ans=min(ans,(ll)pq.size());
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ttt=1;
cin>>ttt;
while(ttt--){
solve();
}
//solve();
return 0;
}
|
a[i]替换为 a[i-1] - a[i] + a[i+1] 想到差分…
定义d[i]=a[i]-a[i-1]
d[i+1]=a[i+1]-a[i]
替换后 d[i]=a[i+1]-a[i]
d[i+1]=a[i]-a[i+1]
可以看出,替换即为交换两边的差分,且由于a[i-1]与a[i+1]的奇偶性相同,所以a[i]的奇偶性并不会改变
对于一段 1为奇数 2为偶数 1 2 1 2 1 2 1 相邻的差分是可以任意交换的
操作的本质是：在差分数组中，只有相邻且奇偶性相同的两个元素可以交换。
因此字典序最小转化为 可以进行操作部分 的 差分数组 升序
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
cin>>n;
vector<ll> a(n+1,0);
vector<ll> d(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
d[i]=a[i]-a[i-1];
}
int l=2;
int r=l;
while(l<=n){
while(r<=n-1 && (a[r-1]&1) != (a[r+1]&1) ) r++;
if(r==n) break;
l=r;
while(r<=n-1 && ( a[r-1] & 1) == ( a[r+1] & 1 )) r++;
sort(d.begin()+l,d.begin()+1+r);
}
for(int i=1;i<=n;i++){
d[i]=d[i-1]+d[i];
cout<<d[i]<<" ";
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ttt=1;
cin>>ttt;
while(ttt--){
solve();
}
return 0;
}
|