MT2057 门票

简介: MT2057 门票

a739edec75e44938b05bed5f7c801bdf.jpg

02363a59d3a0491e91f56fc63ebbdd95.jpg

思路:


此题是求有多少个区间的平均值>=t, 那么可以把每个值-t。如果新的数列的某个区间的和>=0,那么说明这个区间满足条件。

令新数列的前缀和为b[i],所以求[i, j]区间是否满足条件,即求b[j]-b[i-1]是否>=0,即b[j]>=b[i-1]。

因为j>i>i-1,所以这里即求“伪逆序对”的数量。


扩展知识:


逆序对:i>j a[i]<a[j]      伪逆序对/非逆序对:i>j a[i]>a[j]

方法:归并排序


代码:


1.8/10代码:错误原因:超时

#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e6 + 10;
long long int p = 1e9 + 7;
long long int n, t;
long long int a[N];
long long int b[N];
int main()
{
    cin >> n >> t;
    for (long long int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] -= t;
    }
    for (long long int i = 1; i <= n; i++)
    {
        b[i] = b[i - 1] + a[i];
    }
    long long int ans = 0;
    for (long long int i = 1; i <= n; i++)
    {
        for (long long int j = 1; j <= i; j++)
        {
            if (b[i] - b[j - 1] >= 0)
            {
                ans++;
            }
        }
    }
    cout << ans % p;
}


2.10/10代码:升序排列求逆序对,再用总的-逆序对即为非逆序对个数

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
int p = 1e9 + 7;
ll n, t;
ll a[N], sum[N], q[N];
ll ans = 0;
void merge_sort(int l, int r, ll a[])
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
 
    merge_sort(l, mid, a);
    merge_sort(mid + 1, r, a);
 
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j])
        {
            q[k++] = a[j++];
            ans += mid - i + 1; // 升序排列,求逆序数
            ans %= p;
        }
        else
        {
            q[k++] = a[i++];
        }
    }
    while (i <= mid)
        q[k++] = a[i++];
    while (j <= r)
        q[k++] = a[j++];
    for (i = l, j = 0; i <= r; i++, j++)
    {
        a[i] = q[j];
    }
}
 
int main()
{
    cin >> n >> t;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] -= t;
        sum[i] = sum[i - 1] + a[i];
    }
    merge_sort(0, n, sum);
    cout << (n * (n + 1) / 2 - ans) % p;
    return 0;
}


3.10/10代码,直接降序求非逆序对个数

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
int p = 1e9 + 7;
ll n, t;
ll a[N], sum[N], q[N];
ll ans = 0;
void merge_sort(int l, int r, ll a[])
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
 
    merge_sort(l, mid, a);
    merge_sort(mid + 1, r, a);
 
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
        {
            q[k++] = a[j++];
            ans += mid - i + 1; // 降序排列,求非逆序数
            ans %= p;
        }
        else
        {
            q[k++] = a[i++];
        }
    }
    while (i <= mid)
        q[k++] = a[i++];
    while (j <= r)
        q[k++] = a[j++];
    for (i = l, j = 0; i <= r; i++, j++)
    {
        a[i] = q[j];
    }
}
 
int main()
{
    cin >> n >> t;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] -= t;
        sum[i] = sum[i - 1] + a[i];
    }
    merge_sort(0, n, sum);
    cout << ans % p;
    return 0;
}


相关文章
|
JavaScript 前端开发 搜索推荐
分享57个JS返回顶部特效,总有一款适合您
分享57个JS返回顶部特效,总有一款适合您
186 1
|
11月前
|
Web App开发 运维 安全
1Panel:一个现代化、开源的 Linux 服务器运维管理面板
1Panel:一个现代化、开源的 Linux 服务器运维管理面板
404 0
|
前端开发
前端移动端开发中对手机机型的判断
在日常开发中,前端往往需要根据用户的手机系统类型去做相应的操作,执行对应的代码。
716 56
|
消息中间件 Java
RabbitMQ 实战教程(三) 发布/订阅
RabbitMQ 实战教程(三) 发布/订阅
278 0
RabbitMQ 实战教程(三) 发布/订阅
|
SQL C# 数据库
C# 读取Sql Server中的NULL返回什么?
C# 读取Sql Server中的NULL返回什么?
185 0
C# 读取Sql Server中的NULL返回什么?
|
C#
WPF,强制捕获鼠标事件,鼠标移出控件外依然可以执行强制捕获的鼠标事件
原文:WPF,强制捕获鼠标事件,鼠标移出控件外依然可以执行强制捕获的鼠标事件 在WPF中,只有鼠标位置在某个控件上的时候才会触发该控件的鼠标事件。例如,有两个控件都注册了MouseDown和MouseUp事件,在控件1上按下鼠标,不要放开,移动到控件2上再放开。
2397 0
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1275 5
|
2天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1291 87