【每日编程-273期】快速排序
著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定 $N = 5$, 排列是1、3、2、4、5。则：
1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
类似原因，4 和 5 都可能是主元。
因此，有 3 个元素可能是主元。
输入格式：
输入在第 1 行中给出一个正整数 （）；第 2 行是空格分隔的 个不同的正整数，每个数不超过 。
输出格式：
在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
5
1 3 2 4 5输出样例：
3
1 4 5代码实现：
#include <iostream>
#include <algorithm>
#include <vector>
int v[100000];
using namespace std;
//灰灰考研@一航代码
int main()
{
int n, max = 0, cnt = 0;
scanf( "%d", &n );
vector<int> a( n ), b( n );
for ( int i = 0; i < n; i++ )
{
scanf( "%d", &a[i] );
b[i] = a[i];
}
sort( a.begin(), a.end() );
for ( int i = 0; i < n; i++ )
{
if ( a[i] == b[i] && b[i] > max )
v[cnt++] = b[i];
if ( b[i] > max )
max = b[i];
}
printf( "%d\n", cnt );
for ( int i = 0; i < cnt; i++ )
{
if ( i != 0 )
printf( " " );
printf( "%d", v[i] );
}
printf( "\n" );
return(0);
}
划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁就赢了，输家罚一杯酒。两人同赢或两人同输则继续下一轮，直到唯一的赢家出现。
下面给出甲、乙两人的划拳记录，请你统计他们最后分别喝了多少杯酒。
输入格式：
输入第一行先给出一个正整数 （），随后 行，每行给出一轮划拳的记录，格式为：
甲喊 甲划 乙喊 乙划其中喊是喊出的数字，划是划出的数字，均为不超过 100 的正整数（两只手一起划）。
输出格式：
在一行中先后输出甲、乙两人喝酒的杯数，其间以一个空格分隔。
输入样例：
5
8 10 9 12
5 10 5 10
3 8 5 12
12 18 1 13
4 16 12 15输出样例：
1 2