首页 > 其他分享 >C - Sum of Numbers Greater Than Me

C - Sum of Numbers Greater Than Me

时间:2023-12-04 22:22:05浏览次数:33  
标签:Me map valpos valsum Sum long int Than first

C - Sum of Numbers Greater Than Me

https://atcoder.jp/contests/abc331/tasks/abc331_c

 

思路

由于 值 可以是重复的, 需要记录每出现的值 对应的位置 , 记录在 map<int, vector<int>> valpos;

此处利用了map key的自动排序属性, 把所有值 进行从小到大 做了排序,

然后根据valpos,将每个值计算 前缀和, 记录在 map<int, long long> valsum;

每个值的和 = 值 * 出现的次数

 

最后根据前缀和valsum, 计算每个位置 的答案(大于此位置值的所有值的和), 记录在 long long ABiggerSum[1000010];

打印 long long ABiggerSum[1000010];

 

Code

https://atcoder.jp/contests/abc331/submissions/48138824

 

int N;
int A[1000010];
map<int, vector<int>> valpos;
map<int, long long> valsum;
long long ABiggerSum[1000010];

int main()
{
    cin >> N;
    
    for(int i=1; i<=N; i++){
        cin >> A[i];
        valpos[A[i]].push_back(i);
    }

    map<int, vector<int>>::iterator it, itprev;
    for(it=valpos.begin(); it!=valpos.end(); it++){
        int thisval = it->first;
        vector<int> indice = it->second;

        long long thissum = thisval * indice.size();
        if (it == valpos.begin()){
            valsum[it->first] = thissum;
        } else {
            valsum[it->first] = valsum[itprev->first] + thissum;
        }
        
        itprev = it;
    }

    long long total = valsum[itprev->first];
    for(it=valpos.begin(); it!=valpos.end(); it++){
        int thisval = it->first;
        vector<int> indice = it->second;
        
        long long thissum = valsum[thisval];
        long long biggersum = total - thissum;
        
        for(auto one_pos: indice){
            ABiggerSum[one_pos] = biggersum;
        }
    }

    for(int i=1; i<=N; i++){
        cout << ABiggerSum[i] << " ";
    }

    return 0;
}

 

标签:Me,map,valpos,valsum,Sum,long,int,Than,first
From: https://www.cnblogs.com/lightsong/p/17876164.html

相关文章

  • E - Set Meal
    E-SetMealhttps://atcoder.jp/contests/abc331/tasks/abc331_e 思路定义vector<int>v[100005];对于cd对进行group操作,得到每个aidish对应不可能的bjdish的cost值的集合 对bdishcost数组进行排序,小的在前,大的在后,对于每一个adish,使用v寻找第一个排除......
  • 基于ATMega16的流水灯实例(汇编)
    本例在ATMega16上,利用汇编程序实现一个流水灯,主要讨论寄存器移位及软件延时的使用方法。本例中的八个LED电路通过限流电阻及跳线帽接在PA端口,电路如下图所示。完整的汇编代码如下。 .INCLUDE"M16DEF.INC".DEFTMP=R16;定义一个R16寄存器的别名(R不能......
  • 2023ICCV_FSI Frequency and Spatial Interactive Learning for Image Restoration in
     三.Network 1.  2.FLB:没看懂是怎么分离的水平和竖直方向 3.SLB:每一层保留一半的通道特征用于细化,其余的在特征重构后输出(没看懂)。Multi-distillationNetwork 超分辨网络的Multi-distillationNetwork(2019ACMMM_LightweightImageSuper-ResolutionwithIn......
  • 基于ATMega16的最小系统及其开发环境简介
    AVR实验例程用的最小系统如下图所示,芯片采用ATMega16A,主晶振频率为8MHz,异步晶振频率为32768Hz,系统采用JTAG接口调试及下载程序。以上仅是最小系统的电路图,后续例程中使用到的额外电路会在例程中给出相应的模块电路。AVRStudio集成开发环境(IDE)是专门用于开发AVR单片机的开发软......
  • 【刷题笔记】124. Binary Tree Maximum Path Sum
    题目Givena non-empty binarytree,findthemaximumpathsum.Forthisproblem,apathisdefinedasanysequenceofnodesfromsomestartingnodetoanynodeinthetreealongtheparent-childconnections.Thepathmustcontain atleastonenode anddoes......
  • CF1442D Sum 题解
    题目链接点击打开链接题目解法\(n^3\)的\(dp\)是显然的但我们没用到\(a\)不降的性质考虑一个很妙的结论:最优选法中,至多只有一个序列取了且未取满为什么?如果最优情况下,存在选且未选满的序列为\(a,b\),第一个未选的元素为\(x,y\)如果\(a_x>a_{pre_y}\),那么选\(x\)......
  • 新建vue项目,并引入element ui和axios的步骤
    一、新建vue项目(1)win+R进入命令行 使用cmd (2)切换到需要创建vue项目的盘符下  直接D:就能切换到D盘 (3)使用vueui指令进入图形化创建vue项目的界面(注意在创建项目的时候,命令行不能关闭)  之后就在浏览器的界面中进行创建  点击下方的“在此创建新项目”(4)......
  • docker container中变更timezone
    当前使用了playwright官方python镜像: https://playwright.dev/python/docs/docker但在实际使用时,时间总是显示为UTC0时间 正好相差8个小时,前面是jenkins打印时间,后面部分是container内部时间查了网上各种方法,总共有几种:1,直接加命令行:dockerrun-eTZ=Asia/Shanghai2......
  • k8删Terminating 状态的namespace
     开启 proxy [root@master01tmp]#kubectlproxy--port=6880Startingtoserveon127.0.0.1:6880[root@master01~]#kubectlgetnskubesphere-system-ojson>m12.json[root@master01~]#vim12.json修改将spec的 finalize置空,如下所示  curl-k-H"Conte......
  • 在 Sublime Text 4 for macOS 中使用多个光标
    在SublimeText4formacOS中使用多个光标在SublimeText4formacOS中使用多个光标(也称为多点编辑)是一项非常强大的功能,允许您在多个地方同时进行编辑。以下是一些常用的方法来使用多个光标:1.添加额外的光标按住Command键并点击:您可以在需要添加新光标的每个位置按......