Codeforces Round 723

C Potions (Easy Version)

题意：给一个数组a 每次可以加a[i]或者减a[i],但不能为0，问最多可以操作多少次

题解：带反悔的贪心

当a[i]>=0时必定加上

而当a[i]<0时

若a[i]+sum>=0，则我们先将a[i]加上让次数最大化

若a[i]+sum<0 我们查看堆顶是否有大于该值的更大的负数 有的话我们将其替换 这样获得的值增加 而且次数不变

code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
int a[N];
void solve()
{
    priority_queue<int> q;
    int n, sum = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x >= 0)
            sum += x, ans++;
        else
        {
            if (sum + x >= 0)
            {
                sum += x;
                q.push(-x);
                ans++;
            }
            else
            {
                if(q.size()){
                   int last = q.top();
                if (last > -x)
                {
                    q.pop();
                    q.push(-x);
                    sum += last;
                    sum += x;
                } 
                }

            }
        }
       // cout << sum << " " << ans << endl;
    }
    cout << ans << endl;
}
signed main()
{
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

D Kill Anton

题意 给一个字符串s 找一个s的排列字符串t，使得t相对于s的逆序对数量最多

题解：最优解是相同字母全部在一起时贡献最大 (不会证 手玩一下样例感觉是这样 如果不相邻总能找到更多的逆序对 让贡献增加)

枚举四种不同字母的全排列再求一次逆序对即可

时间复杂度O(24nlogn)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int st[N], tr[N], num[N], b[N], c[N];
int a[N], n;
char out[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int y)
{
    for (int i = x; i <= n; i += lowbit(i))
    {
        tr[i] += y;
    }
}
ll query(int x)
{
    ll res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
    {
        res += tr[i];
    }
    return res;
}
void cle()
{
    for (int i = 1; i <= 110; i++)
    {
        tr[i] = 0;
        st[i] = 0;
        num[i] = 0;
        b[i] = 0;
        c[i] = 0;
    }
}
void solve()
{

    string s;
    cin >> s;
    s = ' ' + s;
    n = s.size() - 1;
    cle();
    int cnt = 0;
    for (int i = 1; i < s.size(); i++)
    {
        if (!st[s[i] - 'A' + 1])
        {
            st[s[i] - 'A' + 1] = 1;
            a[++cnt] = s[i] - 'A' + 1;
        }
        num[s[i] - 'A' + 1]++;
        b[i] = s[i] - 'A' + 1;
    }

    ll  ans = 0, res = 0;
    sort(a + 1, a + 1 + cnt);
    do
    {
        for (int i = 1; i <= n; i++)
            c[i] = b[i];
        for (int i = 1; i <= n; i++)
            tr[i] = 0;
        int si = 0;
        res = 0;
        int mp[110];
        // for (int i = 1; i <= cnt; i++)
        //     mp[a[i]] = 0;
        for (int i = 1; i <= cnt; i++)
            mp[a[i]] = ++si;
        //对于原串求逆序对
        for (int i = 1; i <= n; i++)
            b[i] = mp[b[i]]; //求bi的逆序对个数

        for (int i = n; i >= 1; i--)
        {
            res += query(b[i] - 1); //小于等于b[i]-1的数
            add(b[i], 1);
        }
        //  cout << res << endl;
        if (res >= ans)
        {
            ans = res;
            int cou = 0;
            for (int i = 1; i <= cnt; i++)
            {
                for (int j = 1; j <= num[a[i]]; j++)
                {
                    out[++cou] = a[i] - 1 + 'A';
                }
            }
        }
        // cout << endl;
        for (int i = 1; i <= n; i++)
            b[i] = c[i];
    } while (next_permutation(a + 1, a + 1 + cnt));
    for (int i = 1; i <= n; i++)
        cout << out[i];
    cout << "\n";
    // system("pause");
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
}