震惊！！！某初中生竟30min一蓝两紫一黑！！！

我才不会说我是标题党

题目地址

Solution

都是一个东西啦，其实思路差不多，注意几个点

注意数据类型
注意数据范围
注意输入格式
多测不清空，爆零两行泪
题目要求（最大，最小）
正负

接下来就是愉快的代码时间

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll d[500005],ans;
 5 bool vis[500005];
 6 int n,k,t,t1;
 7 int r[500005],l[500005];
 8 struct node{ 
 9     int id;
10     ll val;
11     node(ll Val,int Id){val=Val,id=Id;}
12     bool operator < (node a) const {
13         return val<a.val; 
14     }
15 };
16 void del(int x){
17     l[x]=l[l[x]];
18     r[x]=r[r[x]];
19     r[l[x]]=l[r[x]]=x;
20 }
21 priority_queue<node> q;
22 int main(){
23     scanf("%d%d",&n,&k);
24     for(int i=1;i<=n;i++)scanf("%lld",&d[i]),l[i]=i-1,r[i]=i+1,q.push(node(d[i],i));
25     for(int i=1;i<=k;i++){
26         while(vis[q.top().id])
27          q.pop();
28         node tmp=q.top();q.pop();
29         if(tmp.val<0)break;
30         ans+=tmp.val;
31         vis[l[tmp.id]]=vis[r[tmp.id]]=1;
32         d[tmp.id]=d[l[tmp.id]]+d[r[tmp.id]]-d[tmp.id];
33         q.push(node(d[tmp.id],tmp.id));
34         del(tmp.id);
35     }
36     printf("%lldn",ans);
37 }

种树

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[100005],ans;
bool vis[100005];
int n,k,t,t1;
int r[100005],l[100005];
struct node{
    ll val;
    int id;
    node(ll Val,int Id){val=Val,id=Id;}
    bool operator < (node a) const {
        return val>a.val; 
    }
};
void del(int x){
    l[x]=l[l[x]];
    r[x]=r[r[x]];
    r[l[x]]=l[r[x]]=x;
}
priority_queue<node> q;
int main(){
    //freopen("a.in","r",stdin);
    int T;
    scanf("%d",&T); 
    while(T--){
        ans=0;
        scanf("%d %d %d",&n,&k,&t);
        fill(vis+1,vis+n+1,0);
        for(int i=1;i<n;i++)scanf("%d",&t1),d[i]=t1-t,t=t1;
        d[0]=d[n]=2e9;
        for(int i=1;i<n;i++)l[i]=i-1,r[i]=i+1,q.push(node(d[i],i));
        for(int i=1;i<=k;i++){
           while(vis[q.top().id])
            q.pop();
           node tmp=q.top();q.pop();
           ans+=tmp.val;
           vis[l[tmp.id]]=vis[r[tmp.id]]=1;
           d[tmp.id]=d[l[tmp.id]]+d[r[tmp.id]]-d[tmp.id];
           q.push(node(d[tmp.id],tmp.id));
           del(tmp.id);
        }
        while(!q.empty())q.pop();
        printf("%lldn",ans);
    }
}

数据备份

祝大家早日A了这道题（滑稽

原文链接: https://www.cnblogs.com/coder-cjh/p/11417659.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/301618

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

震惊！！！某初中生竟30min一蓝两紫一黑！！！

相关推荐