首页 > 其他分享 >8016: 重新排序 差分

8016: 重新排序 差分

时间:2023-08-16 22:33:38浏览次数:35  
标签:int ll 整数 查询 差分 数组 8016 排序 Ri

描述

 

给定一个数组 A 和一些查询 Li,Ri,求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊,于是他想重新排列一下数组,使得最终每个查询结果的和尽可能地大。

小蓝想知道相比原数组,所有查询结果的总和最多可以增加多少?

 

 

输入

 

输入第一行包含一个整数 n。

第二行包含 n 个整数 A1,A2,⋅⋅⋅,An相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行,每行包含两个整数 Li、Ri相邻两个整数之间用一个空格分隔。

 

 

输出

 

输出一行包含一个整数表示答案。

 

 

样例输入

 

5
1 2 3 4 5
2
1 3
2 5

样例输出

 4

提示

样例解释:

原来的和为 6+14=20,重新排列为 (1,4,5,2,3) 后和为 10+14=24,增加了 4。

 

数据范围

对于 30%的评测用例,n,m≤50;

对于 50%的评测用例,n,m≤500;
对于 70%的评测用例,n,m≤5000;
对于所有评测用例,1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤n。

显然贪心思路就是让出现次数越多的位置上的数越大
由于只需要修改不需要查询,因此我们可以通过 一维差分 统计每个位置的次数,对差分做前缀和即可得到每个位置出现次数的数组
原先查询结果的总和 = 每个位置出现次数 * 位置上的数
排列后查询结果的总和 = 每个位置出现次数 * 重新排列后位置上对应的数,由于数的大小与次数成正比,因此只要分别对两个数组排序即

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,inf = 0x3f3f3f3f;
ll a[N],d[N];
ll n,m;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    cin >> m;
    while(m--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        d[l]++;
        d[r+1]--;
    }
    ll sum1 = 0,sum2 = 0;
    for(int i=1;i<=n;i++)
    {
        d[i]+=d[i-1];
        sum1+=a[i]*d[i];
    }
    sort(a+1,a+1+n);
    sort(d+1,d+1+n);
    for(int i=1;i<=n;i++)
        sum2+=a[i]*d[i];
    cout << sum2 - sum1;
     return 0;
}

 

标签:int,ll,整数,查询,差分,数组,8016,排序,Ri
From: https://www.cnblogs.com/jyssh/p/17636395.html

相关文章

  • 4877: 火柴排队 归并排序
    描述  涵涵有两盒火柴,每盒装有n根火柴,每根火柴都有一个高度。现在将每盒中的火柴各自排成一列,同一列火柴的高度互不相同,两列火柴之间的距离定义为:Σ(ai-bi)^2,i=1~n,其中ai表示第一列火柴中第i个火柴的高度,bi表示第二列火柴中第i个火柴的高度。每列火柴中相邻两根火柴的......
  • Python 实现排序算法
    常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。冒泡排序冒泡排序(BubbleSort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复......
  • 4866: 瑞士轮 归并排序
    描述  2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前,以及所有比赛结束后,都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛开始前......
  • 5708: 逆序对 归并排序
    描述  给定 一个序列,求其逆序对的总数。所谓逆序对是指:序列a中存在两个元素a[i]和a[j],满足 i<j 且a[i]>a[j],则a[i]和a[j]为一个逆序对。  输入  第一行为正整数n(n<=100000)。第二行有n个正整数,最大不超过1000000。  输出  输出逆序对的总数。......
  • Java中List排序的4种方法
    在开发ERP或电商系统中,经常会遇到内容加密,生成签名,展示页面列表等功能场景,这个时候我们需要在Java程序中对List集合进行排序操作。排序的常见方法有以下4种:使用Comparable进行排序;使用Comparator进行排序;JDK8以上的环境,可以使用Stream流进行排排序;JD......
  • 冒泡排序
    冒泡排序-时间复杂度为O(n2)publicclassDemo{publicstaticvoidmain(String[]args){int[]a={3,23,12,3,423,22,4,534,66,34};System.out.println(Arrays.toString(sort(a)));}//冒泡排序//1比较数组中,两个相邻的元素,如......
  • 计数排序(Python)
    defcounting(data):"data里的value作为计数数组counts的index,然后把counts的value转换成data的index"#计数列表,存储每个值有多少个,以data的值作为索引,所以数组长度以最大值+1为准counts=[0foriinrange(max(data)+1)]#同时给数组赋初值0,等会逐个计数......
  • MySQL8.0 JSON的对比、排序和索引
    (目录)JSON的对比和排序JSON值可以通过=,<,<=,>,>=,<>,!=,<=>操作符来进行对比JSON不支持BETWEEN,IN(),GREATEST(),LEAST(),可以通过将JSON转换为其他数据类型来使用这些操作符。JSON值的对比在两个级别上进行,先进行数据类型的对比,如果类型相同,再进行值的对比。类型可以......
  • 冒泡排序
    #include<iostream>usingnamespacestd;intmain(){intn;cin>>n;inta[n];for(inti=0;i<n;i++){ cin>>a[i]; }for(inti=1;i<n;i++){for(intj=1;j<=n-i;j++){if(a[j-1]<a[j]){......
  • 基数排序
    博客地址:https://www.cnblogs.com/zylyehuo/#-*-coding:utf-8-*-#O(n)O(kn)#NBO(nlogn)importrandomdefpartition(li,left,right):tmp=li[left]whileleft<right:whileleft<rightandli[right]>=tmp:#从右面找比tmp小的数......