头像

ghostq




离线:2小时前


活动打卡代码 AcWing 125. 耍杂技的牛

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n;
std::pair<int,int>cow[50010];
int main(){
#ifdef LOCAL
    freopen("耍杂技的牛.in","r",stdin);
    freopen("耍杂技的牛.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=0;i<n;i++){
        int s,w;
        std::cin>>w>>s;
        cow[i]={w+s,w};
    }
    std::sort(cow,cow+n);
    int res=-2000000000,sum=0;
    for(int i=0;i<n;i++){
        int s=cow[i].first-cow[i].second,w=cow[i].second;
        res=std::max(res,sum-s);
        sum+=w;
    }
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n,q[100010];
int main(){
#ifdef LOCAL
    freopen("货仓选址.in","r",stdin);
    freopen("货仓选址.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=0;i<n;i++)std::cin>>q[i];
    std::sort(q,q+n);
    int res=0;
    for(int i=0;i<n;i++)res+=abs(q[i]-q[n/2]);
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n,t[100010];
int main(){
#ifdef LOCAL
    freopen("排队打水.in","r",stdin);
    freopen("排队打水.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=0;i<n;i++)std::cin>>t[i];
    std::sort(t,t+n);
    std::reverse(t,t+n);
    long long res=0;
    for(int i=0;i<n;i++)res+=t[i]*i;
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int main(){
#ifdef LOCAL
    freopen("合并果子.in","r",stdin);
    freopen("合并果子.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n;
    std::cin>>n;
    std::priority_queue<int,std::vector<int>,std::greater<int> >heap;
    while(n--){
        int x;
        std::cin>>x;
        heap.push(x);
    }
    int res=0;
    while(heap.size()>1){
        int a=heap.top();
        heap.pop();
        int b=heap.top();
        heap.pop();
        res+=a+b;
        heap.push(a+b);
    }
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n;
struct Range{
    int l,r;
    bool operator<(const Range&W)const{return l<W.l;}
}range[100010];
int main(){
#ifdef LOCAL
    freopen("区间覆盖.in","r",stdin);
    freopen("区间覆盖.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int st,ed;
    std::cin>>st>>ed>>n;
    for(int i=0;i<n;i++){
        int l,r;
        std::cin>>l>>r;
        range[i]={l,r};
    }
    std::sort(range,range+n);
    int res=0;
    bool success=false;
    for(int i=0;i<n;i++){
        int j=i,r=-2000000000;
        while(j<n&&range[j].l<=st){
            r=std::max(r,range[j].r);
            j++;
        }
        if(r<st){
            res=-1;
            break;
        }
        res++;
        if(r>=ed){
            success=true;
            break;
        }
        st=r;
        i=j-1;
    }
    if(!success)res=-1;
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n;
struct Range{
    int l,r;
    bool operator<(const Range&W)const{return l<W.l;}
}range[100010];
int main(){
#ifdef LOCAL
    freopen("区间分组.in","r",stdin);
    freopen("区间分组.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        std::cin>>l>>r;
        range[i]={l,r};
    }
    std::sort(range,range+n);
    std::priority_queue<int,std::vector<int>,std::greater<int> >heap;
    for(int i=0;i<n;i++){
        auto r=range[i];
        if(heap.empty()||heap.top()>=r.l)heap.push(r.r);
        else{
            heap.pop();
            heap.push(r.r);
        }
    }
    std::cout<<heap.size();
    return 0;
}



ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n;
struct Range{
    int l,r;
    bool operator<(const Range&W)const{return r<W.r;}
}range[100010];
int main(){
#ifdef LOCAL
    freopen("最大不相交区间数量.in","r",stdin);
    freopen("最大不相交区间数量.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=0;i<n;i++)std::cin>>range[i].l>>range[i].r;
    std::sort(range,range+n);
    int res=0,ed=-2000000000;
    for(int i=0;i<n;i++)
        if(ed<range[i].l){
            res++;
            ed=range[i].r;
        }
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n;
struct Range{
    int l,r;
    bool operator<(const Range&W)const{return r<W.r;}
}range[100010];
int main(){
#ifdef LOCAL
    freopen("区间选点.in","r",stdin);
    freopen("区间选点.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=0;i<n;i++)std::cin>>range[i].l>>range[i].r;
    std::sort(range,range+n);
    int res=0,ed=-2000000000;
    for(int i=0;i<n;i++)
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    std::cout<<res<<std::endl;
    return 0;
}


活动打卡代码 AcWing 901. 滑雪

ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n,m,g[310][310],f[310][310],dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dp(int x,int y){
    int&v=f[x][y];
    if(v!=-1)return v;
    v=1;
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&g[x][y]>g[a][b])v=std::max(v,dp(a,b)+1);
    }
    return v;
}
int main(){
#ifdef LOCAL
    freopen("滑雪.in","r",stdin);
    freopen("滑雪.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)std::cin>>g[i][j];
    memset(f,-1,sizeof f);
    int res=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)res=std::max(res,dp(i,j));
    std::cout<<res<<std::endl;
    return 0;
}



ghostq
4个月前
//#define LOCAL
#include<bits/stdc++.h>
int n,h[6010],e[6010],ne[6010],idx,happy[6010],f[6010][2];
bool has_fa[6010];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u){
    f[u][1]=happy[u];
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=std::max(f[j][0],f[j][1]);
    }
}
int main(){
#ifdef LOCAL
    freopen("没有上司的舞会.in","r",stdin);
    freopen("没有上司的舞会.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    for(int i=1;i<=n;i++)std::cin>>happy[i];
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        std::cin>>a>>b;
        add(b,a);
        has_fa[a]=true;
    }
    int root=1;
    while(has_fa[root])root++;
    dfs(root);
    std::cout<<std::max(f[root][0],f[root][1])<<std::endl;
    return 0;
}