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;
}


目录
打赏
0
0
0
0
30
分享
相关文章
1Panel:一个现代化、开源的 Linux 服务器运维管理面板
1Panel:一个现代化、开源的 Linux 服务器运维管理面板
332 0
前端移动端开发中对手机机型的判断
在日常开发中,前端往往需要根据用户的手机系统类型去做相应的操作,执行对应的代码。
694 56
WPF,强制捕获鼠标事件,鼠标移出控件外依然可以执行强制捕获的鼠标事件
原文:WPF,强制捕获鼠标事件,鼠标移出控件外依然可以执行强制捕获的鼠标事件 在WPF中,只有鼠标位置在某个控件上的时候才会触发该控件的鼠标事件。例如,有两个控件都注册了MouseDown和MouseUp事件,在控件1上按下鼠标,不要放开,移动到控件2上再放开。
2366 0
kde
|
4天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
2767 7
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
522 0
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
759 7

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问