算法1 (双向链表+优先队列) O(NlogN)[蓝桥杯和Acwing都能AC]
- 因为涉及到删除数后, 还要找到其前后的值, 所以不难想到得用双链表
- 我用优先队列
pair<value, pos>
维护最小值 - 但同时我们需要一个st[]来记录当前值是否为真的值, 比如测样中, 我们把第一个1删了, 位于第二个位置的4就得+1, 如果!如果!一次pq.top()为第2个位置(值为4), 那这个值就是假的, 我们得把它的值+1(从pos=1来的那个1), 同时让st[2]=0;再把这个值塞会pq, 这不能算作一次操作(k不能–) 只有当pq弹出的是位置, 在st[]是0, 这个值才是真值(k–);
- 时间复杂度分析: 有K次操作, 每次操作平均时间复杂度是O(logN) 优先队列出队嘛, 所以总的O(NlogN)
C++ 代码
/* 整数删除:
* 我们用双向链表存数据 + 优先队列(pair<value, pos>)
* 用map会TLE, 所以, map-->st[]
*/
#include <iostream>
#include <queue>
#include <unordered_map>
#include <functional>
#define lli long long int
#define pii pair<lli,int>
using namespace std;
const int N=500010;
int bef[N], aft[N]; //双向链表
lli e[N];
int n, k;
//unordered_map<int, lli> rem; // pair<pos, addtion> 记录pos位置的数应该增加多少
lli rem[N];
priority_queue<pii, vector<pii>, greater<pii> > pq; // pair<value, pos>
int main() {
scanf("%d%d", &n, &k);
for(int i=1;i<=n;i++){
scanf("%ld", &e[i]);
bef[i]=i-1; aft[i]=i+1;
pq.push({e[i], i});
}
while(k) {
lli value=pq.top().first;
int pos=pq.top().second;
pq.pop();
if(!rem[pos]) { //为真值
rem[bef[pos]]+=value, rem[aft[pos]]+=value; //改值
aft[bef[pos]]=aft[pos]; //前一个的next为当前的next
e[bef[pos]]+=value;
bef[aft[pos]]=bef[pos]; //后一个的befor要等于当前的bef
e[aft[pos]]+=value;
e[pos]=-1;
k--;
}
else { //当前为假值
lli addtion=rem[pos];
value+=addtion;
rem[pos]=0;
pq.push({value, pos});
}
}
for(int i=1;i<=n;i++) if(e[i]!=-1) printf("%lld ", e[i]); puts("");
return 0;
}
算法2 (线段树+双向链表) $O(NlogN)$ [只有ACWing能AC]
- 想到要频繁的改值, (在线操作), 也很容易想到线段树, 维护一个求区间最小值的线段树即可;
- 时间复杂度分析: 有K次操作, 每次logN(线段树的modify和query都是logN的复杂度)所以总共 O(NlogN), 但常数很大, ACWing能过(给了3秒), 蓝桥杯那边只给了1s, 所以蓝桥杯过不了) 线段树+常数≈10e9, 很极限;
C++ 代码
// 怎么快速找到前后的点??? -----双向链表!!!!
#include <iostream>
#define lli long long int
#define pii pair<lli,int>
using namespace std;
const int N=500010;
const lli INF=9223372036854775807;
int n, k;
struct Element{
int be, ne;
lli value;
int idx;// idx 为当前的位置
}arr[N];
struct Node{
int l, r;
pii minn={-1,-1}; // pair<value, pos> // 这里的pos指的是cnt的值, 其前一个值为e[be[cnt]]
}tr[4*N];
pii resmin(pii a, pii b) { return a.first<=b.first?a:b; }
void pushup(int u) { tr[u].minn=resmin(tr[u*2].minn,tr[u*2+1].minn); }
struct Node make_Node(int _l, int _r, lli _value, int _pos) {
struct Node newnode;
newnode.l=_l;
newnode.r=_r;
newnode.minn.first=_value;
newnode.minn.second=_pos;
return newnode;
}
void build(int u, int l, int r) {
if(l==r) tr[u]=make_Node(l,r,arr[l].value, arr[l].idx);
else {
tr[u]=make_Node(l,r,0,0);
int mid=l+r>>1;
build(u*2,l,mid);build(u*2+1,mid+1,r); //注意1
pushup(u);
}
}
void modify(int u, int poss, pii x) {
if(tr[u].l==tr[u].r) tr[u].minn=x;
else {
int mid= tr[u].l+tr[u].r>>1;
if(poss<=mid) modify(u*2,poss,x); //注意2
else modify(u*2+1,poss,x);
pushup(u);
}
}
pii query(int u, int l, int r) {
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].minn; //注意3
else {
int mid= tr[u].l+tr[u].r>>1;
pii res={0,INF};
if(l<=mid) res=resmin(query(u*2, l, r), res);
if(r>mid) res=resmin(query(u*2+1, l, r), res);
return res;
}
}
// for test
void printTR(void) {
for(int i=1;i<=n;i++) printf("[%d,%d], value:%ld, pos:%d\n", tr[i].l, tr[i].r, tr[i].minn.first, tr[i].minn.second);
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
int t;scanf("%ld",&t);
arr[i]={i-1,i+1, t, i};
}
// for(int i=1;i<=n;i++) cout<<arr[i].value<<" "; puts("");
build(1,1,n);
for(int i=1;i<=k;i++) {
pii aim=query(1,1,n);
//要找到真正的左位置, 和右位置
int l=arr[aim.second].be;
int r=arr[aim.second].ne;
arr[aim.second].value=INF; // 将这个值删去
modify(1,aim.second,{arr[aim.second].value, arr[aim.second].idx});
arr[l].ne=arr[aim.second].ne;
arr[r].be=arr[aim.second].be;
if(l>=1) {
arr[l].value+=aim.first;
modify(1,l,{arr[l].value, arr[l].idx});// 左边+上这个值
}
if(r<=n) {
arr[r].value+=aim.first;
modify(1,r,{arr[r].value, arr[r].idx});// 右边+上这个值
}
// cout<<"value:"<<aim.first<<" pos:"<<aim.second<<endl;
// printf("l: %d, r: %d\n", l, r);
// for(int i=1;i<=n;i++) printf("%d ",arr[i].value); puts("");
// printTR();
}
for(int i=1;i<=n;i++) if(arr[i].value!=INF) printf("%ld ",arr[i].value);
return 0;
}
关于在ACWing线段树快于优先队列, 个人猜测试测样的原因, 手写堆的话, 优先队列绝对更佳