PTA 7-32 说反话-加强版 （C/C++)

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过500 000的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用若干个空格分开。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子，并且保证单词间只有1个空格。

输入样例：

Hello World   Here I Come

结尾无空行

输出样例：

Come I Here World Hello

结尾无空行

分析：做题之间先想思路，这道题通常的做法是建立一个二维字符数组 / (vector 数组 ），然后依次遍历原字符数组，碰到空格跳过，将单词复制到新建的数组中。细想一下，这么做太麻烦了，复制过程既耗时又占用空间，况且本题字符串长度很长，不妨想个新方法，使得尽量在原数组上改动，而不复制。

可以试试这么干：依次遍历原字符数组，将空格替换成字符串结束符，那么每个单词的终止位置就知道了，所以只需要记录单词的起始位置就行了。（这个方法对于没学C++的同学也好理解的。）最后逆序输出，代码如下：

#include 
#include 
using namespace std;
char str[500001];int sign[300001]; //最多只有字符长度一半的单词，sign是记录每个单词的起始位置
int main()
{
    cin.getline(str,500001);
	int k=0,flag=1; // flag=1标志前面一位是空格
    int len=strlen(str);
    for (int i=0;i=0;i--) {
        printf("%s",str+sign[i]);  //逆序输出
        if (i) printf(" "); 
   }
}