前缀和+排序——cf1043E

落日映苍穹つ 2023-10-12 08:22 74阅读 0赞

先不考虑第二个条件

要求i和所有其他人的分数和最小，选择x还是y，可以推出一个公式，即差xi-yi小的j都选y，反之都选x

那么按照xi-yi排序即可

然后再考虑第二个条件，做减法就行

/*
    xi+yj<xj+yi
    xi-yi<xj-yj
    xi-yi值小取xi
    xi-yi值大取yi 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define N 300005
    struct Node {
        ll x,y,id;
    }p[N],q[N];
    int n,m;
    ll ans[N],sumx[N],sumy[N];
    int cmp(Node a,Node b){
        return a.x-a.y<b.x-b.y;}
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&p[i].x,&p[i].y),p[i].id=i;
        for(int i=1;i<=n;i++)q[i]=p[i];
            
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++){
            sumx[i]=sumx[i-1]+p[i].x;
            sumy[i]=sumy[i-1]+p[i].y;
        }
        for(int i=1;i<=n;i++){
            ans[p[i].id]+=(i-1)*p[i].y;
            ans[p[i].id]+=sumx[i-1];
            ans[p[i].id]+=(n-i)*p[i].x;
            ans[p[i].id]+=sumy[n]-sumy[i];
        }
        
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            Node a=q[u],b=q[v];
            ll sum=min(a.x+b.y,a.y+b.x);
            ans[u]-=sum;
            ans[v]-=sum;
        }
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
    }

转载于:https://www.cnblogs.com/zsben991126/p/11441649.html

发表评论取消回复

表情：

评论列表（有 0 条评论，74人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF——1189C——（前缀和+数学思维）

题目链接][Link 1] /********* 根据题意就是 sum(l..r)整除10 对于 a，b，c，d 这个数列注：/ 为整除 sum/10 = ...

朴灿烈づ我的快乐病毒、/ 2024年04月18日 08:17/ 0 赞/ 155 阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 179 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 157 阅读

相关【构造+拓扑排序】CF1385E

[Problem - 1385E - Codeforces][] 题意： ![e5bb03d5f2804bc7871a58b507e1dcca.png][] ![4249

r囧r小猫/ 2024年03月17日 11:37/ 0 赞/ 148 阅读

相关前缀和+排序——cf1043E

先不考虑第二个条件要求i和所有其他人的分数和最小，选择x还是y，可以推出一个公式，即差xi-yi小的j都选y，反之都选x 那么按照xi-yi排序即可然后再考虑第二个条

落日映苍穹つ/ 2023年10月12日 08:22/ 0 赞/ 75 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 117 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 209 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 313 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 313 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 370 阅读