题目：
给你一个01串，现在你可以（或者不用）选取其中一个元素进行一次反转操作0-1，1-0；从而使得串中的逆序对个数最多。
题目链接：codeforce origin problem
思路：
1. 如何统计逆序对的个数？
从后向前扫描，定义zero，记录0的个数，如果遇到1，则逆序对增加的个数就等于的此时zero。
点击查看代码
vector<int>a;
ll f(decltype(a)& d)
{
ll zero = 0, sum = 0;
rfor(i, d.size() - 1, 0)
{
//cout << d[i] << " ";
if ( d[i] == 0 )
zero++;
else sum += zero;
}
return sum;
}
2.如何进行一次反转使得逆序对个数最多？
我们考虑0-1反转，让逆序对数量更多，则应该让下标最小的0filp为1，这样子，逆序对个数最多。
我们考虑1-0反转，让逆序对数量更多，则应该让下标最小的1filp为0，这样子，逆序对个数最多。
AC代码
//注意事项：记得开longlong，避免溢出
// 其次，不用经过反转01，可能已经是最大的了，需要先做记录
vector<int>a;
ll f(decltype(a)& d)
{
ll zero = 0, sum = 0;
rfor(i, d.size() - 1, 0)
{
//cout << d[i] << " ";
if ( d[i] == 0 )
zero++;
else sum += zero;
}
return sum;
}
void solve()
{
ll n;
cin >> n;
a.resize(n);
ifor(i, 0, n - 1)
{
cin >> a[i];
}
ll res;
res = f(a);
ifor(i, 0, n - 1)
{
if ( a[i] == 0 )
{
a[i] = 1;
ll s1 = f(a);
res = max(s1, res);
a[i] = 0;
break;
}
}
rfor(i, n-1, 0)
{
if ( a[i] == 1 )
{
a[i] = 0;
ll s1 = f(a);
res = max(s1, res);
a[i] = 1;
break;
}
}
cout << res<<endl;
a.clear();
}
int main(int args, char** argv)
{
/*ios::sync_with_stdio(false);
cin.tie(nullptr);
cin.tie(nullptr);*/
long t;
cin >> t;
while ( t-- )
{
solve();
}
return 0;
}
![P1880 [NOI1995] 石子合并 题解](https://www.kunjuke.com/file/css/thumb/3.jpg/280-180.jpg)
![P5020 [NOIP2018 提高组] 货币系统 题解](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
