这个题原始的O(N^2)必然tle，看见100000这么大规模就知道他必然要暗算这种解法了。即使发现了所求的序列最长必定不会超过2F-1，O(NF)的算法也难保不会被一堆F=50000,N=100000的数据搞死。所以肯定要找O(NlogN)或者O(NlogF)级的算法。我现在是没这个能耐去设计这种算法啦，所以就上网去找了一篇paper，到portal.acm.org搜一下maximum average subsequence应该就可以找到了。

今天下午我问了uni这个怎么做，他说的好像是蒙可能的平均值，用最大子段和代替最大子段平均，在蒙的基础上用二分来修正。至于怎么用凸包来做就不知道了，今天我写了一个类似Quick Hull的办法也是tle。

• 不是蒙啦 (18) uni 2005-04-18 22:27:20
  • Re:不是蒙啦 (28) uni 2005-04-18 22:28:39
  • 是二分不是蒙~~~~~~ (57) frkstyc 2005-04-18 22:30:59
    • Re:是二分不是蒙~~~~~~ (89) uni 2005-04-19 12:24:23
      • 没懂，您能详细讲一下做法吗？ (93) TN 2005-04-19 12:27:35
        • Re:同问,我完全是蒙过的 (0) ArXoR 2005-04-19 12:28:48
          • Re:同问,我完全是蒙过的 (19) scu05p27 2006-03-22 22:45:29
      • uni的原话，没看懂，被迫猜意思 (85) frkstyc 2005-04-19 13:02:36
        • Re:uni的原话，没看懂，被迫猜意思 (8) uni 2005-04-19 13:05:33
          • Re:uni的原话，没看懂，被迫猜意思 (42) uni 2005-04-19 13:10:10
            • 第二、三行很容易懂，第一行很难懂：（用）二分（试探）平均值，再减去这个平均值…… (46) frkstyc 2005-04-19 13:15:08
              • Re:第二、三行很容易懂，第一行很难懂：（用）二分（试探）平均值，再减去这个平均值…… (84) uni 2005-04-19 13:21:17
                • Re:第二、三行很容易懂，第一行很难懂：（用）二分（试探）平均值，再减去这个平均值…… (135) frkstyc 2005-04-19 13:23:14
                  • Re:第二、三行很容易懂，第一行很难懂：（用）二分（试探）平均值，再减去这个平均值…… (33) uni 2005-04-19 13:38:26
• O(NF)果然也超时 (337) frkstyc 2005-04-19 13:03:24
  • 过了，不过Zhouyuan似乎有O(N)的方法 (0) TN 2005-04-24 12:37:33
    • 不过很麻烦的样子...... (0) TN 2005-04-24 16:43:44
      • 写一下？ (0) frkstyc 2005-04-24 16:48:18
    • zhouyuan?他写过这题么？ (0) palmtenor 2005-04-24 16:50:16
      • 哦，凸包，我似乎悟到了 (0) palmtenor 2005-04-24 16:51:18
        • 对，就是类似凸包，似乎是在2004的论文里写的 (0) TN 2005-04-24 16:51:53
          • 04他写的不是最小表示么？ (0) palmtenor 2005-04-24 16:56:10
          • O(N)的算法可以拿去发paper了，我找到的paper也只是O(NlogM)的 (0) frkstyc 2005-04-24 17:18:14
            • 我觉得也是，凸包就已经nlogn了 (0) palmtenor 2005-04-24 17:48:05
              • 是凸包+一个小技巧，我去找找ZhY的论文 (0) TN 2005-04-24 17:58:39