题解 P1816 【忠诚】

life_w_back · 2018-05-04 17:13:07 · 题解

先按照动归做的，结果的了九十分，代码比较好理解；

就超了4毫秒。。。。。。。。。

90分代码；

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main(){
    int m,n,t,k,ans=9999999;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d%d",&t,&k);
        for(int j=t;j<=k;j++){
            ans=min(ans,a[j]);
        }
        printf("%d ",ans);
        ans=9999999;
    }
    return 0;
}

下面是AC程序；

主要是快排，先把账目排一遍，再找提问范围里靠前的，找到后就输出；（比较好理解）

上代码

#include<bits/stdc++.h>
using namespace std;
struct fff{
  int x,y;  
};
fff a[100001];
bool cmp(fff l,fff v){
    return l.x<v.x;
}
int main(){
    int m,n,t,k;
    scanf("%d%d",&m,&n);
        for(int i=1;i<=m;i++){
            scanf("%d",&a[i].x);
            a[i].y=i;    //为每个账目编号；
        }
        sort(a+1,a+1+m,cmp);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&t,&k);
            for(int j=1;j<=m;j++){
                if(a[j].y>=t&&a[j].y<=k){
                    printf("%d ",a[j].x);
                    break;     //一个小优化；
                }
            }
        }
    return 0;
}