P1816 忠诚

admin · 发表于 2018-4-21 17:59:42

https://www.luogu.org/problem/P1816

题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

输入输出格式
输入格式：
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

第二行为m个数,分别是账目的钱数

后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。

输出格式：
输出文件中为每个问题的答案。具体查看样例。

输入输出样例
输入样例#1：
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
输出样例#1：
2 3 1

吴语林 · 发表于 2018-7-29 23:58:19

#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[100020],minn[400040],m,n,x,y,t;
void biuld_xian(int l,int r,int o)
{
if(l==r)
{
minn[o]=a[l];
return;
}
int mid=(l+r)>>1;
biuld_xian(l,mid,o*2);
biuld_xian(mid+1,r,o*2+1);
minn[o]=min(minn[o*2],minn[o*2+1]);
}
int query(int L,int R,int l,int r,int o)
{
if(L<=l&&r<=R) return minn[o];
int mid=(l+r)>>1;
int a1=0x3f3f3f3f,a2=0x3f3f3f3f;
if(L<=mid) a1=query(L,R,l,mid,o*2);
if(R>mid) a2=query(L,R,mid+1,r,o*2+1);
return min(a1,a2);
}
int main()
{
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
biuld_xian(1,n,1);
while(t--)
{
scanf("%d%d",&x,&y);
printf("%d ",query(x,y,1,n,1));
}
return 0;
}

复制代码

liubo · 发表于 2018-7-30 23:45:00

#include<iostream>
using namespace std;
const int maxn = 100005;
struct node{
int minv;
int l,r;
int mid(){
return (l + r)/2;
}
}t[300010];
int ans = 1 << 30,m,n;
void buildTree(int root,int l,int r){
node &n = t[root];
n.l = l;
n.r = r;
n.minv = 1 << 30;
if(l == r)return;
buildTree(root * 2 + 1,l,n.mid());
buildTree(root * 2 + 2,n.mid() + 1,r);
}
void insertNum(int root,int i,int v){
node &n = t[root];
if(n.l == n.r && n.l == i){
n.minv = v;
return;
}
n.minv = min(n.minv,v);
if(i > n.mid())
insertNum(root * 2 + 2,i,v);
else insertNum(root * 2 + 1,i,v);
}
void ask(int root,int l,int r){
node &n = t[root];
if(n.l == l && n.r == r){
ans = min(ans,n.minv);
return;
}
if(l > n.mid())
ask(root * 2 + 2,l,r);
else if(r <= n.mid())
ask(root * 2 + 1,l,r);
else{
ask(root * 2 + 1,l,n.mid());
ask(root * 2 + 2,n.mid() + 1,r);
}
}
int main(){
cin >> m >> n;
buildTree(0,1,m);
for(int i = 1;i <= m;i++){
int k;
cin >> k;
insertNum(0,i,k);
}
for(int i = 1;i <= n;i++){
int l,r;
cin >> l >> r;
ans = 1 << 30;
ask(0,l,r);
cout << ans << " ";
}
return 0;
}

复制代码

黄煦喆 · 发表于 2018-7-31 09:22:09

#include<iostream>
using namespace std;
int m,n,t,s,e;
struct node
{
int l,r,minv;
node *pleft,*pright;
int mid()
{
return l+(r-l>>1);
}
}tree[400010];
int cnt;
void build(node *root,int l,int r)
{
root->l=l;
root->r=r;
root->minv=9999999;
if(l==r)return;
else
{
int Mid=root->l+(r-l>>1);
cnt++;
root->pleft=tree+cnt;
cnt++;
root->pright=tree+cnt;
build(root->pleft,l,Mid);
build(root->pright,Mid+1,r);
}
}
void _insert(node *root,int i,int v)
{
if(root->l==i&&root->r==i)
{
root->minv=v;
return;
}
else
{
root->minv=min(v,root->minv);
if(i<=root->mid())_insert(root->pleft,i,v);
else if(i>root->mid())_insert(root->pright,i,v);
}
}
int query(node* root,int a,int b)
{
if(root->l==a&&root->r==b)return root->minv;
if(b<=root->mid())return query(root->pleft,a,b);
else if(a>root->mid())return query(root->pright,a,b);
else
{
int ans1=9999999,ans2=9999999;
ans1=query(root->pleft,a,root->mid());
ans2=query(root->pright,root->mid()+1,b);
return min(ans1,ans2);
}
}
int main()
{
cin>>m>>n;
build(tree,1,m);
for(int i=1;i<=m;i++)
{
cin>>t;
_insert(tree,i,t);
}
for(int i=1;i<=n;i++)
{
cin>>s>>e;
cout<<query(tree,s,e)<<' ';
}
return 0;
}

复制代码

zhwang · 发表于 2018-7-31 10:04:30

#include<cstdio>
#include<algorithm>
#define INF 999999999
using namespace std;
int n,m;
int a[100001];
struct node
{
int left;
int right;
int _min;
}tree[400001];
int l,r;
void setup(int root,int start,int end)
{
tree[root].left=start;
tree[root].right=end;
if(start==end)
{
tree[root]._min=a[start];
}
else
{
setup(root*2,start,(start+end)/2);
setup(root*2+1,(start+end)/2+1,end);
tree[root]._min=min(tree[root*2]._min,tree[root*2+1]._min);
}
}
int findout(int root,int start,int end)
{
if(tree[root].left==start&&tree[root].right==end)
{
return tree[root]._min;
}
int answer=INF;
if(start>=tree[root*2+1].left)
{
answer=findout(root*2+1,start,end);
}
else
{
if(end<=tree[root*2].right)
{
answer=findout(root*2,start,end);
}
else
{
answer=min(findout(root*2,start,tree[root*2].right),findout(root*2+1,tree[root*2+1].left,end));
}
}
return answer;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
setup(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
printf("%d ",findout(1,l,r));
}
return 0;
}

复制代码

admin · 发表于 2019-11-9 21:26:22

楼上大佬们都是用线段树再做，其实还有更简单的写法，ST表。

#include <bits/stdc++.h>
using namespace std;
const int mn=100010;
int n,k,i,j,x,y,z;
int a[mn],f[mn][100];
void check()
{
for (int i=1; i<=n; i++,cout<<endl)
for (int j=0; i+(1<<j)-1<=n; j++) cout<<setw(4)<<f[i][j];
}
int main()
{
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>a[i];
///递推得到F数组
for (i=1; i<=n; i++) f[i][0]=a[i];
for (j=1; (1<<j)<=n; j++)
for (i=1; i+(1<<j)-1<=n; i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); ///注意边界
///check();
while (k--)
{
cin>>x>>y;
z=log2(y-x+1);
cout<<min(f[x][z],f[y-(1<<z)+1][z])<<" ";
}
return 0;
}

复制代码

秀木于林 · 发表于 2019-12-20 17:54:30

#include<iostream>
#include<cmath>
using namespace std;
int a[100100],f[100100][20],l,r,n,m;
int pow2(int x)
{
int s=1;
for(int i=1; i<=x; i++) s*=2;
return s;
}
int main()
{
cin>>n>>m;
int t=log2(n);
for(int i=1;i<=n;i++)
cin>>f[i][0];
for(int j=1;j<=t;j++)
for(int i=1;i<=n;i++)
if(i+(1<<j)-1<=n)
///f[i][j]=min(f[i][j-1],f[i+pow2(j-1)][j-1]);
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
/*
for(int i=1;i<=n;i++,cout<<endl)
for(int j=1;j<=20;j++)
if(i+pow2(j)-1<=n)
cout<<f[i][j]<<' ';
*/
for(int k=1;k<=m;k++)
{
cin>>l>>r;
int j=log2(r-l+1);
cout<<min(f[l][j],f[r-(1<<j)+1][j])<<' ';
}
return 0;
}

复制代码

		自动登录	找回密码
密码			立即注册