3 条题解

  • 3
    @ 2026-10-24 11:12:17

    三倍 经验

    其实可以用优先队列,只是多带个 log 而已

    code:

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+5;
    int n,h[N],w[N],k,d;
    struct node{
    	int sum,h,id;
    };
    bool operator < (node a,node b){
    	if(a.sum!=b.sum) return a.sum>b.sum;
    	return a.h<b.h;
    }
    node makenode(int x,int y,int z){
    	node aa;
    	aa.sum=x; aa.h=y; aa.id=z;
    	return aa;
    }
    priority_queue<node> pq;
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
    	cin>>n>>k>>d;
    	for(int i=1;i<=n;i++) cin>>h[i]>>w[i];
    	pq.push(makenode(w[1],h[1],1));
    	for(int i=2;i<=n;i++){
    		node y=pq.top();
    		while(i-y.id>k){
    			pq.pop(); y=pq.top();
    		}
    		if(h[i]>h[y.id]) pq.push(makenode(y.sum+w[i]+d,h[i],i));
    		else pq.push(makenode(y.sum+w[i],h[i],i));
    	}
    	node y=pq.top();
    	while(y.id!=n){
    		pq.pop(); y=pq.top();
    	}
    	cout<<y.sum;
    	return 0;
    }
    
    • @ 2026-10-24 11:48:39

      %%%

    • @ 2026-10-24 11:51:30

      pqpq 竟然能过?

      我赛时写了 pqpq 感觉不行,结果删掉重写 dddldddl,调代码花了 1h1h。

    • @ 2026-10-26 9:32:22

      %%%

信息

ID
929
时间
1000ms
内存
256MiB
难度
6
标签
(无)
递交数
52
已通过
18
上传者