Codeforces Round #585 (Div. 2)
这场比赛和机房大佬一起打的，打的我心态爆炸。
这道题目比较简单，直接贪心即可，不过直接贪心比较麻烦，所以我们可以用队列来辅助贪心。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define one first
#define two second
using namespace std;
priority_queue<ll>q;
priority_queue<ll,vector<ll>,greater<ll> >q2;
ll a1,a2,k1,k2,n;
int main()
{
scanf("%lld%lld%lld%lld%lld",&a1,&a2,&k1,&k2,&n);
for (int i=1;i<=a1;i++)
{
q.push(k1);
q2.push(k1);
}
for (int i=1;i<=a2;i++)
{
q.push(k2);
q2.push(k2);
}
ll num=n;
while (!q.empty()&&num--)
{
ll k=q.top();
q.pop();
if (k-1>0) q.push(k-1);
}
printf("%d ",a1+a2-(int)q.size());
num=n;
while (!q2.empty()&&num--)
{
ll k=q2.top();
q2.pop();
if (k-1>0) q2.push(k-1);
}
printf("%d
",a1+a2-(int)q2.size());
return 0;
}
就是这道题目搞得我心态爆炸，其实当时也想出来类似的思路，就是想复杂了，可能是思路太过僵化。
我们发现以负数为界，分成各个区间，每个区间的第一个数为负数，第一个区间除外。
我们将区间分为奇偶两种，我们发现只要不经过负数，前面的区间（包括这个区间 (<=i) 的部分）的对后面这个区间的贡献是相同的，只有经过了负数区间贡献才会相反。
于是我们记录一下到当前数区间的不同种类的数目，然后判一下符号和贡献就可以了。
其实也可以只算一种的区间个数，然后另一个用 (n*(n+1)/2) 减出来。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+100;
int n;
ll ans;
int main()
{
scanf("%d",&n);
int num1=1,num2=0,p=1;
for (int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if (x<0) p=-p;
if (p>0)
{
ans+=num1;
num1++;
}
else
{
ans+=num2;
num2++;
}
}
printf("%lld %lld
",(ll)n*(n+1)/2-ans,ans);
return 0;
}
需要掌握的地方：用 (i) 和小于 (i) 的数据直接算到 (i) 的贡献。
这道题是一个比较简单的构造题，但是因为 (B) 题心态爆炸，所以也没有花太多时间去做，直到最后才写了一发，少加了一个 (1) ，导致连样例都没过。
因为字符集只有两种 (a) 和 (b) ，所以比较显然只有上下两个字符串当前字母不同的情况才会考虑换字母。
考虑要交换字母只有两种情况
第一种
[a a
]
[b b
]
这样的直接换 (1 2) 或者 (2 1) 很明显就是最优解。
第二种
[a b
]
[b a
]
这样你就会发现，将 (1 1) 或 (2 2) 换一下就成了上面的那种情况。
所以按照这个贪心策略跑一下，判一下无解就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
char a[N],b[N];
int tp[N],v1[N],v2[N];
int n,num1,num2;
int main()
{
scanf("%d",&n);
scanf("%s%s",a+1,b+1);
for (int i=1;i<=n;i++)
{
tp[(int)a[i]]++;
tp[(int)b[i]]++;
if (a[i]=='a'&&b[i]=='b')
v1[++num1]=i;
if (a[i]=='b'&&b[i]=='a')
v2[++num2]=i;
}
if (tp['a']%2!=0||tp['b']%2!=0)
{
printf("-1
");
return 0;
}
if (num1%2==0&&num2%2==0)
{
printf("%d
",num1/2+num2/2);
int mid=num1/2;
for (int i=1;i<=mid;i++)
printf("%d %d
",v1[i],v1[i+mid]);
mid=num2/2;
for (int i=1;i<=mid;i++)
printf("%d %d
",v2[i],v2[i+mid]);
return 0;
}
int p=0;
p+=num1%2;
p+=num2%2;
if (p==1)
{
printf("-1
");
return 0;
}
printf("%d
",num1/2+(num2+1)/2+1);
printf("%d %d
",v1[num1],v1[num1]);
v2[++num2]=v1[num1];
num1--;
int mid=num1/2;
for (int i=1;i<=mid;i++)
printf("%d %d
",v1[i],v1[i+mid]);
mid=num2/2;
for (int i=1;i<=mid;i++)
printf("%d %d
",v2[i],v2[i+mid]);
return 0;
}
教训：不要死磕一道题，当一道题没有思路或比较难写的时候可以换一道题，一道题比较难写的时候考虑换一种思路。
不要太心急，要仔细核对样例，冷静分析。
当时空限制允许的时候可以用数据结构来简化代码。
适当放弃。