华师一附中OI组

标题: tyvj忠诚求解 我做了好久都只能过七个点 [打印本页]
作者: hr567    时间: 2014-10-22 21:43
标题: tyvj忠诚求解 我做了好久都只能过七个点
本帖最后由 hr567 于 2014-10-22 21:45 编辑

      老管家是一个聪明能干的人。他为财主工作了整整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


——我不生产题目，我只是题目的搬运工。
作者: admin    时间: 2014-10-23 10:49
若是这道题的规模，直接排序后查找应该没有问题的。
作者: hr567    时间: 2014-10-23 22:02
第九个点总是过不了……
  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. }
复制代码
作者: hr567    时间: 2014-10-23 22:04
结果：

测试数据 #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
作者: wsk12345    时间: 2014-11-7 20:49
这个题其实不需要线段树
作者: wsk12345    时间: 2014-11-7 20:50
本帖最后由 wsk12345 于 2014-11-7 20:54 编辑
  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;

  34. }
复制代码
作者: wsk12345    时间: 2014-11-7 20:52
这里就别用cin了，经不起大数据轰炸，之前用cin超时，换了scanf()就好了



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2