题目1126：打印极值点下标

题目描述：

在一个整数数组上，对于下标为i的整数，如果它大于所有它相邻的整数，
或者小于所有它相邻的整数，则称为该整数为一个极值点，极值点的下标就是i。

输入：

每个案例的输入如下：

有2×n+1行输入：第一行是要处理的数组的个数n；
对其余2×n行，第一行是此数组的元素个数k(4<k<80)，第二行是k个整数，每两个整数之间用空格分隔。

输出：

每个案例输出为n行：每行对应于相应数组的所有极值点下标值，下标值之间用空格分隔。

样例输入：

3
10
10 12 12 11 11 12 23 24 12 12
15
12 12 122 112 222 211 222 221 76 36 31 234 256 76 76 
15
12 14 122 112 222 222 222 221 76 36 31 234 256 76 73

样例输出：

0 7
2 3 4 5 6 10 12
0 2 3 10 12 14

C++代码：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
        int n;
        while(cin >> n)
        {
                while(n--)
                {
                        int k,i;
                        cin >> k;
                        vector<int> vv(k);
                        for(i = 0;i < k;i++) cin >> vv[i];
                        vector<int> out;
                        out.reserve(k);
                        if(vv[0] < vv[1]||vv[0] > vv[1]) out.push_back(0);
                        for(i = 1;i <= k-2;i++)
                        {
                                if(vv[i] > vv[i-1]&&vv[i] > vv[i+1]) out.push_back(i);
                                if(vv[i] < vv[i-1]&&vv[i] < vv[i+1]) out.push_back(i);
                        }
                        if(vv[k-1] < vv[k-2]||vv[k-1] > vv[k-2]) out.push_back(k-1);
                        for(i = 0;i < out.size() - 1;i++) cout << out[i] << " ";
                        cout << out[i] << endl;
                }
        }
        return 0;
}
/**************************************************************
    Problem: 1126
    User: Carvin
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1520 kb
****************************************************************/

C++另一种思路：

<div class="container"><div class="line number1 index0 alt2"><code class="c preprocessor">#include<iostream></code></div><div class="line number2 index1 alt1"><code class="c keyword bold">using</code> <code class="c keyword bold">namespace</code> <code class="c plain">std;</code></div><div class="line number3 index2 alt2"> </div><div class="line number4 index3 alt1"><code class="c keyword bold">void</code> <code class="c plain">f(</code><code class="c color1 bold">int</code> <code class="c plain">a[],</code><code class="c color1 bold">int</code> <code class="c plain">n)</code></div><div class="line number5 index4 alt2"><code class="c plain">{</code></div><div class="line number6 index5 alt1"><code class="c spaces">    </code><code class="c color1 bold">int</code> <code class="c plain">i=0;</code></div><div class="line number7 index6 alt2"><code class="c spaces">    </code><code class="c keyword bold">if</code><code class="c plain">(a[0]!=a[1])</code></div><div class="line number8 index7 alt1"><code class="c spaces">        </code><code class="c plain">cout<<0;</code></div><div class="line number9 index8 alt2"><code class="c spaces">    </code><code class="c keyword bold">for</code><code class="c plain">(i=1;i<n-1;i++)</code></div><div class="line number10 index9 alt1"><code class="c spaces">    </code><code class="c plain">{</code></div><div class="line number11 index10 alt2"><code class="c spaces">        </code><code class="c keyword bold">if</code><code class="c plain">((a[i]>a[i-1])&&(a[i]>a[i+1])||(a[i]<a[i-1]&&a[i]<a[i+1]))</code></div><div class="line number12 index11 alt1"><code class="c spaces">            </code><code class="c plain">cout<<</code><code class="c string">" "</code><code class="c plain"><<i;</code></div><div class="line number13 index12 alt2"><code class="c spaces">    </code><code class="c plain">}</code><code class="c comments">//for</code></div><div class="line number14 index13 alt1"><code class="c spaces">    </code><code class="c keyword bold">if</code><code class="c plain">(a[n-1]!=a[n-2])</code></div><div class="line number15 index14 alt2"><code class="c spaces">        </code><code class="c plain">cout<<</code><code class="c string">" "</code><code class="c plain"><<n-1;</code></div><div class="line number16 index15 alt1"><code class="c spaces">    </code><code class="c plain">cout<<endl;</code></div><div class="line number17 index16 alt2"><code class="c plain">}</code></div><div class="line number18 index17 alt1"><code class="c color1 bold">int</code> <code class="c plain">main()</code></div><div class="line number19 index18 alt2"><code class="c plain">{</code></div><div class="line number20 index19 alt1"><code class="c spaces">   </code><code class="c color1 bold">int</code> <code class="c plain">n;</code></div><div class="line number21 index20 alt2"><code class="c spaces">   </code><code class="c color1 bold">int</code> <code class="c plain">a[100];</code></div><div class="line number22 index21 alt1"><code class="c spaces">   </code><code class="c color1 bold">int</code> <code class="c plain">i,j,k;</code></div><div class="line number23 index22 alt2"><code class="c spaces">   </code><code class="c keyword bold">while</code><code class="c plain">(cin>>n)</code></div><div class="line number24 index23 alt1"><code class="c spaces">   </code><code class="c plain">{</code></div><div class="line number25 index24 alt2"><code class="c spaces">       </code><code class="c keyword bold">for</code><code class="c plain">(i=0;i<n;i++)</code></div><div class="line number26 index25 alt1"><code class="c spaces">       </code><code class="c plain">{</code></div><div class="line number27 index26 alt2"><code class="c spaces">         </code><code class="c plain">cin>>k;</code></div><div class="line number28 index27 alt1"><code class="c spaces">         </code><code class="c keyword bold">for</code><code class="c plain">(j=0;j<k;j++)</code></div><div class="line number29 index28 alt2"><code class="c spaces">         </code><code class="c plain">{</code></div><div class="line number30 index29 alt1"><code class="c spaces">             </code><code class="c plain">cin>>a[j];</code></div><div class="line number31 index30 alt2"><code class="c spaces">         </code><code class="c plain">}</code><code class="c comments">//for</code></div><div class="line number32 index31 alt1"><code class="c spaces">         </code><code class="c plain">f(a,k);</code></div><div class="line number33 index32 alt2"><code class="c spaces">       </code><code class="c plain">}</code><code class="c comments">//for</code></div><div class="line number34 index33 alt1"><code class="c spaces">   </code><code class="c plain">}</code><code class="c comments">//while</code></div><div class="line number35 index34 alt2"><code class="c spaces">   </code><code class="c keyword bold">return</code> <code class="c plain">1;</code></div><div class="line number36 index35 alt1"><code class="c plain">}</code><code class="c comments">//main</code></div><div class="line number37 index36 alt2"><code class="c comments">/**************************************************************</code></div><div class="line number38 index37 alt1"><code class="c spaces">    </code><code class="c comments">Problem: 1126</code></div><div class="line number39 index38 alt2"><code class="c spaces">    </code><code class="c comments">User: Carvin</code></div><div class="line number40 index39 alt1"><code class="c spaces">    </code><code class="c comments">Language: C++</code></div><div class="line number41 index40 alt2"><code class="c spaces">    </code><code class="c comments">Result: Presentation Error</code></div><div class="line number42 index41 alt1"><code class="c comments">****************************************************************/</code></div></div>

题目1126：打印极值点下标

原文：http://blog.csdn.net/carvin_zh/article/details/45487947