题解 P1085 【不高兴的津津】

Acorasick · 2017-02-10 21:36:52 · 题解

这是一道很简单的试题。我们先考虑做这道题的数据结构。很显然，题目的要求是我们要询问每天的不高兴值是否大于8，或者是否可以大于max，所以很显然，处理区间询问用线段树非常合适。

代码如下：

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int maxv[N];
int a[N],n=7;
inline void pushup(int o){maxv[o]=max(maxv[o*2],maxv[o*2+1]);}
void build(int o,int l,int r){
    int mid=(l+r)/2;
    if(l==r){maxv[o]=a[l];return;}
    build(o*2,l,mid);build(o*2+1,mid+1,r);
    pushup(o);
}
int querymax(int o,int l,int r,int ql,int qr){
    int mid=(l+r)/2,ans=-1;
    if(ql<=l&&r<=qr)return maxv[o];
    if(ql<=mid)ans=max(ans,querymax(o*2,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,querymax(o*2+1,mid+1,r,ql,qr));
    return ans;
}
int main(){
    for(int i=1;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);a[i]=x+y;
    }
    build(1,1,n);
    bool flag=false;int maxn=0,day=-1;
    for(int i=1;i<=n;i++){
        int ans=querymax(1,1,n,i,i);
        if(ans<8)continue;
        if(ans>maxn)maxn=ans,day=i;
    }
    if(day==-1)puts("0");else printf("%d\n",day);
    return 0;
}

显然，这是一道水题，非常适合入门线段树。