当前位置：首页 > ops >正文

P1816 忠诚题解

ops 2025/7/20 8:36:48

时隔多年，我又回来了，今天来发一篇题解，纪念我回归的第一天。

老规矩，先看题目：

题目传送门：P1816 忠诚

题目描述

老管家是一个聪明能干的人。他为财主工作了整整 10 年。财主为了让自已账目更加清楚，要求管家每天记 k 次账。由于管家聪明能干，因而管家总是让财主十分满意。

但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚。他把每次的账目按 1,2,3,… 编号，然后不定时地问管家这样的问题：在 a 到 b 号账中最少的一笔是多少？

为了让管家没时间作假，他总是一次问多个问题。

输入格式

第一行输入两个数 m,n，表示有 m 笔账和 n 个问题。
第二行输入 m 个数，分别表示账目的钱数。
接下来 n 行分别输入 n 个问题，每行 2 个数字，分别表示开始的账目编号 a 和结束的账目编号 b。

输出格式

第一行输出每个问题的答案，每个答案中间以一个空格分隔。

输入 #1

10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10

输出 #1

2 3 1

说明/提示

对于 100% 的数据，m≤ $^{^{_{_{10}5}}}$ ，n≤ $^{^{_{_{10}5}}}$ 。

第一次思考结果：

看完题目，我相信大部分人的第一反应都是用暴力解决。但是，你们有没有想过一个问题，就是在最坏情况下时间复杂度会超（眼戳的建议看看时间限制，只有400ms）。管他呢，先试一下暴力，说不定数据太水，直接AC了。

第一种方法：暴力

暴力的写法非常简单，两层循环直接搞定。具体一点，就是每次输入两个数，直接用循环找出最小值，然后输出。下面是代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){cin>>n>>m;int a[n+5];for(int i=1;i<=n;i++){cin>>a[i];}while(m--){int x,y;cin>>x>>y;int minx=INT_MAX;for(int i=x;i<=y;i++){minx=min(minx,a[i]);}cout<<minx<<' ';}return 0;
}

结果：

如果关闭同步流，结果：

还是差了一点。

优化呢？代码：

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;  
}a[100001];
bool cmp(node l,node v){return l.x<v.x;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int m,n,t,k;cin>>m>>n;for(int i=1;i<=m;i++){cin>>a[i].x; a[i].y=i;}sort(a+1,a+1+m,cmp);for(int i=1;i<=n;i++){cin>>t>>k;for(int j=1;j<=m;j++){if(a[j].y>=t&&a[j].y<=k){cout<<a[j].x<<' ';break;}}}return 0;
}

结果：

这测试点真是恶心。

怎么办呢？

第二种方法：ST表

什么是ST表，我这里就不详细说了，不懂的可以自己去查一下。首先，要预处理数组。对于预处理而言 O(n log (n))的时间复杂度，是可以接受的。如果一个区间i的长度为1，那么f[i][0]就为位置i对应的值对于一个长度为2的区间a—>b，我们可以用f[a][1]来表示这个区间的极值，那么对于这个区间而言，f[a][1]的最小值就可以看做min(a,b),即可以看做min(f[a][0],f[a+(1<<0)][0])。

如果我们把左端点记做i，区间长度改为j呢那么f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1];

所有我们在预处理的时候，我们不妨先枚举区间长度j，再枚举区间左端点i，只要能保证i+(1<<j)-1≤n，那么我们便可以将各种区间给预处理出来；

for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){if(i+(1<<j)-1<=n){f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);}}
}

关于查询操作

我们首先读入了某个区间的左端点L，和右端点R；我们并不能保证区间长度（R-L+1）是2的n次方。所以怎么才能用我们预处理的信息呢？（如果用不上预处理他干什么）

对于一个区间的最大值的数值，一个区间肯定只要一个，如果我们用他的两个有重叠的子区间来更新这个区间肯定没有任何问题。

那么我们可以找距离区间长度（R-L+1）最近的一个2的n次方数k，那么我们就可以用 L为左端点，长度为k的区间和以R为右端点，区间长度为k的两个区间长度来更新所求的区间。不懂得可以画画图！

综上所述，对于左端点为L，右端点为R的区间，他的最小值MIN=min(f[L][log2(R-L+1)],f[R-(1<<(log2(R-L+1))+1][log(R-L+1]。

int ask(int l,int r){int k=log2(r-l+1);return min(f[l][k],f[r-(1<<k)+1][k]);
}

所以，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,m,l,r,f[maxn][22];
int ask(int l,int r){int k=log2(r-l+1);return min(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){if(i+(1<<j)-1<=n){f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);}}}for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);printf("%d ",ask(l,r));}return 0;
}

结果：