[暴力题解系列]2023年蓝桥杯-整数删除（30分）

这题暴力最多30分，但是30分也是分，做暴力的人不能贪心，拿到分就是赚了。

​ 这题核心烦人点在于他数据分层断崖，就只有前3个点能做到稳过。用的思路就是链表，但不是用指针存的，而是用数组下标为标记存的，只是我觉得因为这样好写一些。链表方便修改左右连接位置，所以越到后面就越能省下查询的时间

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int n, k;
struct dat{
    int l, r;
    int num;
    bool valid;
}a[500050];
void modify(int i)
{
    a[a[i].l].num += a[i].num;
    if(a[i].r != -1)
        a[a[i].r].num += a[i].num;
    a[a[i].l].r = a[i].r;
    if(a[i].r !=-1)
        a[a[i].r].l = a[i].l;
    a[i].valid = false;
}
int findSmallest()
{
    int p, minn = 1e9, minp;
    for(int i=1; i<=n; i++)
        if(a[i].valid)
        {
            p = i;
            break;
        }
    minp = p;
    while(1)
    {
        //printf("%d ", a[p].num);
        if(a[p].num < minn)
        {
            minp = p;
            minn = a[p].num;
        }
        if(a[p].r == -1)
            break;
        else
            p = a[p].r;
    }
    return minp;
}

void dbgShowChain()
{
    int p;
    for(int i=1; i<=n; i++)
        if(a[i].valid)
        {
            p = i;
            break;
        }
    while(1)
    {
        printf("%d ", a[p].num);
        if(a[p].r == -1)
            break;
        else
            p = a[p].r;
    }
    printf("\n");
}
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i].num);
        a[i].l = i-1, a[i].r = i+1;
        a[i].valid = true;
    }
    a[n].r = -1;
    while(k--)
        modify(findSmallest());
    dbgShowChain();
    return 0;
}
/*
5 3
1 2 3 4 5

3 1
3 2 1
*/