tyvj忠诚求解 我做了好久都只能过七个点

hr567

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

      输入中第一行有两个数m,n。表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。第二行为m个数,分别是账目的钱数。后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。



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


样例输出
2 3 1

——我不生产题目，我只是题目的搬运工。

wsk12345

这里就别用cin了，经不起大数据轰炸，之前用cin超时，换了scanf()就好了

wsk12345

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. struct data                        //用结构体存储数据，value是账目，pos是这个账目的原下标
   
5. {
   
6.     int value,pos;
   
7. };
   
8. int m,n,L,R;
   
9. bool comp(data a,data b)
   
10. {
    
11.     if(a.value<b.value) return true;
    
12.     else return false;
    
13. }
    
14. int main()
    
15. {
    
16.     scanf("%d%d",&m,&n);
    
17.     data a[m];
    
18.     for(int i=0; i<m; ++i)
    
19.     {
    
20.         scanf("%d",&a[i].value);
    
21.         a[i].pos=i;
    
22.     }
    
23.     sort(a,a+m,comp);
    
24.     for(int i=0;i<n;++i)
    
25.     {
    
26.         scanf("%d%d",&L,&R);
    
27.         for(int j=0;j<m;++j)
    
28.         {
    
29.              if((a[j].pos>=L-1)&&(a[j].pos<=R-1)) {cout<<a[j].value<<' ';break;}
    
30.         }
    
31.     }
    
32.     return 0;
    
33. 
    
34. }

复制代码

wsk12345

这个题其实不需要线段树

hr567

结果：

测试数据 #1: Accepted, time=0ms, mem=640KB, score=10
测试数据 #2: Accepted, time=0ms, mem=640KB, score=10
测试数据 #3: Accepted, time=0ms, mem=640KB, score=10
测试数据 #4: Accepted, time=0ms, mem=636KB, score=10
测试数据 #5: Accepted, time=130ms, mem=640KB, score=10
测试数据 #6: Accepted, time=0ms, mem=640KB, score=10
测试数据 #7: Accepted, time=100ms, mem=640KB, score=10
测试数据 #8: Accepted, time=20ms, mem=844KB, score=10
测试数据 #9: Time Limit Exceeded, time=1000ms, mem=784KB, score=0
测试数据 #10: Accepted, time=120ms, mem=636KB, score=10
Time = 1370ms Mem = 844KB Score= 90

hr567

第九个点总是过不了……

1. #include<iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.     long i, j, k, m, n, t;
   
6.     int a[100001];
   
7.     cin >> m >> n;
   
8.     for(i = 1; i <= m; ++i)
   
9.         cin >> a[i];
   
10.     for(i = 1; i <= n; ++i)
    
11.     {
    
12.         cin >> j >> k;
    
13.         for(t = a[j]; j <= k; ++j)
    
14.             if(a[j] < t)t = a[j];
    
15.         cout << t << ' ';
    
16.     }
    
17.     return 0;
    
18. }
    

复制代码

admin

若是这道题的规模，直接排序后查找应该没有问题的。