AcWing 第79场周赛

周赛链接：https://www.acwing.com/activity/content/competition/problem_list/2644/

AcWing 4722. 数列元素

#include <iostream>
using namespace std;

int n;
int main()
{
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i ++)
    {
        sum += i;
        if (sum == n) {
            puts("YES");
            return 0;
        }
    }
    puts("NO");
    return 0;
}

AcWing 4723. 队列

暴力

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int n;
char str[] = {'a', 'b', 'c', 'd', 'e'};

long long level[N];
int ln;

int main()
{
    cin >> n;
    
    if (n <= 5)
    {
        cout << str[n - 1] << endl;
        return 0;
    }
    
    
    long long cur = 5, sum = 5;
    int i;
    for (i = 1; i <= n; i ++)
    {
        cur *= 2;   // 当前层个数
        
        if (sum + cur >= n)
        {
            n -= sum;
            int d = n / (cur / 5);
            cout << str[d];
        }
        
        sum += cur;
        
    }
}

AcWing 4724. 靓号

枚举 模拟

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, k;
string str;

int cnt[N], modify[N], st[N];
vector<string> best_list;
int cost = INF;


string tran(int x)
{
    string s = str;
    
    for (int i = 0; i < s.size(); i ++)
    {
        int p = s[i] - '0';
        if (p > x && modify[p])
        {
            s[i] = x + '0';
            modify[p] --;
        }
    }
    
    for (int i = s.size() - 1; i >= 0; i --)
    {
        int p = s[i] - '0';
        if (p < x && modify[p])
        {
            s[i] = x + '0';
            modify[p] --;
        }
    }
    
    return s;
}

int bfs(int i, int num)    // num: 还需要改变的数量
{
    memset(modify, 0, sizeof modify);
    modify[i] = 0;
    
    int res = 0;   // 代价
    int l = i - 1, r = i + 1;
    
    bool f1, f2;
    f1 = f2 = false;
    
    int last = 0;

    while (l >= 0 && r <= 9 && num)
    {
        if (cnt[l] + cnt[r] < num)
        {
            modify[l] = cnt[l];
            modify[r] = cnt[r];
            res += abs(i - l) * (modify[l] + modify[r]);
            num -= cnt[l] + cnt[r];
            l --, r ++;
        }else 
        {
            res += abs(i - l) * num;
            int k = 0;
            for (int i = 0; k < num && i < str.size(); i ++)
            {
                if (str[i] - '0' == r)
                {
                    modify[r] ++;
                    k ++;
                }
                if (k == num) break;
            }
            
            for (int i = str.size() - 1; k < num && i >= 0; i --)
            {
                if (str[i] - '0' == l)
                {
                    modify[l] ++;
                    k ++;
                }
                if (k == num) break;
            }
            
            num = 0;
        }
        
       
    }
    
    while (r <= 9 && num)
    {
        if (cnt[r] < num)
        {
            num -= cnt[r];
            modify[r] = cnt[r];
        }else 
        {
            f2 = true;
            modify[r] = num;
            num = 0;
        }
        
        res += abs(r - i) * modify[r];
        
        r ++;
    }
    
    while (l >= 0 && num)
    {
        if (cnt[l] < num)
        {
            num -= cnt[l];
            modify[l] = cnt[l];
        }else 
        {
            modify[l] = num;
            num = 0;
        }
        
        res += abs(i - l) * modify[l];
        
        l --;
    }

    return res;
}

int main()
{
    cin >> n >> k;
    cin >> str;
    for (auto x : str) {
        cnt[x - '0'] ++;
    }
    
    // for (int i = 0; i <= 9; i ++)
    // {
    //     printf("%d: %d\n", i, cnt[i]);
    // }
    
    int v;
    for (int c = 0; c <= 9; c ++)
    {
        if (cnt[c] >= k) 
        {
            v = 0;
        }else
        {
            v = bfs(c, k - cnt[c]);
        }
        
        // printf("%d: %d\t", c, v);
        
        if (cost < v) continue;
        
        if (cost > v)
        {
            cost = v;
            best_list.clear();
             
        }
        if (v > 0) best_list.push_back(tran(c));
        else if (v == 0) best_list.push_back(str);
        
        // for (auto x : best_list)
        // {
        //     cout << x << " ";
        // }
        // cout << endl;
    }
    
    sort(best_list.begin(), best_list.end());
    
    cout << cost << endl;
    cout << best_list[0] << endl;
}