整数删除-能看懂系列

解题思路:
第一份代码为通过的代码，借鉴于其处的方法，这边有些大佬的代码可能不太好理解，所以写了这个比较详细的，希望对各位有用；另外这个题我自己也有方法，容易理解但较为繁琐也可惜有4个输出超限，有兴趣的可以试试优化第二份

注意事项:

参考代码:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
const int N = 5e5+10;
//l[i]代表i下标的左边下标，r[i]代表i下标的右边下标,v[i]是i下标的值 例如：
//数据1 2 3 4 5，(1序) 其中v[1] = 1;v[5]=5;l[2]=1(第二个数据的左边是第一个);r[3]=4;(第3个数据的右边是第4个)
ll l[N],r[N],v[N];
int n;
int k;
//删除操作
void del(int id){
//假设数据为1 2 3 4 5
    //把id右边个体的左编号改为id的左编号
    //假设id=2;就让3的左编号(l[3])从原来的2改为1
    l[r[id]] = l[id];
    //把id左边个体的右编号改为id的右编号
    //假设id=2;就让1的右编号(r[1])从原来的2改为3
    r[l[id]] = r[id];
    // 至此最小数就相当于被删除(跟左右编号数组没有了联系)
    //以下 为相邻数据加上最小值
    v[r[id]]+=v[id];
    v[l[id]]+=v[id];
}

int main(){
    cin>>n>>k;
    //初始化0的右编号为1，n+1的左编号为n
    r[0] = 1;
    l[n+1] = n;
    //创建优先队列，将数据排序，top()弹出的值就是最小值
    priority_queue<P,vector<P>,greater<P> > pr;
    //依次输入数据
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        v[i]=a;
        l[i]=i-1;//i左编号为i-1
        r[i]=i+1;//i右编号为i+1
        pr.push({a,i});//将{值，编号}压入最小队列
    }
    while(k--){
        auto [vl,id] = pr.top();//得到最小值vl和对应的编号id
        pr.pop();//删除最小值
        //我们删除时对相邻数据的增加只是针对于v[]数组，最小队列中的值没有改变
        //所以要判断弹出来的最小值是否跟最初值一致
        if(vl!=v[id]){//弹出来的最小值是否跟最初值不同，说明删除其他数据时该数据得到了增加
            pr.push({v[id],id});//重新压入值(更新后的值)和编号进行排序
            k++;//这一次没有进行删除最小值操作，故k自增一次
            continue;
        }
        else del(id);//弹出来的最小值是否跟最初值一致，就执行删除操作
    }
    for(int i=r[0];i<=n;i=r[i]){//输出剩余的数
        cout<<v[i]<<" ";
    }
    return 0;
}

以下是我自己那份不太好的方法，低劣品

#include <iostream>
#include<cstring>
using namespace std;
int n;
int k;
int dex1[500010];
//整体思路：用a[]记录所有数据，数组不利删除，用a[i]=-1代表该数被删除 
//时间的限制主要在于每次寻找最小值，每次都去遍历a[]找到最小值显然会超时 
//把a[]数据集划分为区段，每个区段有k个值 
//例如：5 3
//1 4 2 8 7 就把1 4 2 8 7分为1 4 2的0号区段和8 7的1号区段 
//利用dex1[i]数组 记录i号区段的最小值在a[]数组中的下标
//上面的dex1[0]= 0;dex1[1]=4;
//这样每次操作只需要通过dex1数组 找到最小的那个 
//即使区段原本的最小值发生变化 ，也只需要遍历这区段 

//4个测试集输出超限 

void min_(long long a[]){
	int min =dex1[0];
	int x =0 ; 
	//通过dex1数组 找到最小值下标 min 
	for(int i=1;i<=n/k;i++){
		if(a[dex1[i]]<a[min]){
			min=dex1[i];
			x=i;//x记录的是区段号 
		}
	}
	
	//相邻数修改值 
	
	//从最小值向两边找到第一个值不为-1的元素 即位相邻元素 
	for(int i=min-1;i>=0;i--){
    	if(a[i]!=-1){
    		a[i]+=a[min];
    		break;
		}
	}
    for(int i=min+1;i<n;i++){
    	if(a[i]!=-1){
    		a[i]+=a[min];
    		break;
		}
	}
	a[min]=-1;//删除最小元素 
	
	//不同区段重新查找最小值的下标
	
	//当前的最小值区段 
	long long min1=100000000; 
	for(int i=x*k;i<(x+1)*k&&i<n;i++){
		if(a[i]!=-1&&min1>a[i]){
			min1=a[i];
			dex1[x]=i;
		}
	
	}
	//最小值区段的后一区段 
	min1=100000000;
	if((min+1)%k==0){//最小值为该区段的最后一个，会影响后一个区段的第一个值 
		for(int i=(x+1)*k;i<(x+2)*k&&i<n;i++){
			if(a[i]!=-1&&min1>a[i]){
				min1=a[i];
				dex1[x+1]=i;
			}
		}
	}
	//最小值前一区段 
	min1=100000000;
	if(min%k==0){//最小值为该区段的第一个，会影响前一个区段的最后一个值 
		for(int i=(x-1)*k;i<x*k;i++){
			if(a[i]!=-1&&min1>a[i]){
				min1=a[i];
				dex1[x-1]=i;
			}
		}
	}
}



int main()
{
  // 请在此输入您的代码

  cin>>n>>k;
  long long a[n];
  memset(dex1,-1,sizeof(dex1));
  
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(dex1[i/k]==-1){
    	dex1[i/k]=i;
	}
	if(a[dex1[i/k]]>a[i]){
		dex1[i/k]=i;
	}
  } 
  int x=k;
  while(x--){
    min_(a);
  }

 for(int i=0;i<n;i++){
    if(a[i]!=-1) cout<<a[i]<<" ";
  } 
  return 0;
}