求 大佬 设计 一下 程序 ， 我 的 时间 复杂度 太 大 了
这 种 题目 真 讨厌 啊 ~~ 语文 不 好 ， 要 看 半天 才 能 看懂 他 在 说 什么 。 分析 题目 ， 结果 如下 ： 有 一 个 长度 为 n 的 数 组 ， 起始 位置 是 数 组 头部 pos = 0 ； 每 轮 可以 跳 x 步 ( 1 < = x < = Vi ) 同时 需 满足 （ Di > = n [ pos + x ] ） ； 经过 若干 轮 后 ， 判断 最后 是否 能 到达 数 组 尾部 pos = n - 1 。 给定 m 个 （ Vi ， Di ） ， 判断 每 个 是否 能 到达 。 这个 用 贪婪 算法 ， 每 次 能 跳 多 远 就 跳 多 远 ， 如果 一 步 都 不 能 跳 那么 就 一定 跳 不 出 了 。 这个 问题 时间 复杂度 O ( n ) ~ # include < stdio . h > # include < stdlib . h > int main ( ) { int n , m , pos , step ; int * pool , * Vi , * Di ; scanf ( " % d % d " , & n , & m ) ; / / 读 入 长度 为 n 的 鳄鱼 数据 pool = ( int * ) malloc ( sizeof ( int ) * n ) ; for ( int i = 0 ; i < n ; i + + ) scanf ( " % d " , pool + i ) ; / / 读 入 m 个 装备 的 属性 Vi = ( int * ) malloc ( sizeof ( int ) * m ) ; Di = ( int * ) malloc ( sizeof ( int ) * m ) ; for ( int i = 0 ; i < m ; i + + ) scanf ( " % d % d " , Di + i , Vi + i ) ; / / 求 每 个 装备 是 能 渡过 for ( int i = 0 ; i < m ; i + + ) { pos = 0 ; / / 起始 位置 while ( pos < n - 1 ) { step = 0 ; / / 求 一 次 最多 能 跳 几 步 for ( int j = 1 ; j < = Vi [ i ] & & pos + j < n ; j + + ) if ( Di [ i ] > = pool [ pos + j ] ) step = j ; / / 如果 一 步 都 跳 不 了 ， 那 就 不 再 跳 了 if ( step = = 0 ) break ; else pos + = step ; } / / 输出 结果 if ( pos = = n - 1 ) printf ( " Yes \ n " ) ; else printf ( " No \ n " ) ; } free ( pool ) ; free ( Vi ) ; free ( Di ) ; }
