时间限制：1S 内存限制：64MB

原题链接

描述

输入n个字符串S₁,S₂,...,S_n，对于第i个字符串，你需要回答在前i-1个字符串中，有多少个字符串的字典序严格比S_i小。

输入描述

第一行输入一个数n（1≤n≤100000），接下来输入n行，每行一个字符串。所有单个字符串的长度不超过100000，所有字符串的长度之和不超过200000，所有字符串的字符由26个小写字母构成。

输出描述

输出n行n个数，第i个数表示前i-1个串中，有多少个字符串的字典序严格比S_i小。

示例

输 入：

5
one
one
two
three
four

返回值：

0
0
2
2
0

我的问题代码：时间超了，按照网上那个思路改成C++版本依旧超时，赛码网这个太叛逆了！！！

8/11组用例通过

运行时间：1052 ms

占用内存：5640 kb

用例输入：

50000
……

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


static int insertSortedList(std::vector<std::string>& List, int size, const std::string& key)
{
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int ret = List[mid].compare(key);
        if (ret < 0) // List[mid] < new_word
            left = mid + 1;
        else // List[mid] >= new_word
            right = mid - 1;
    }
    List.insert(List.begin()+left, key);

    return left;
}

int main()
{
    int N;
    std::vector<std::string> List;
    std::cin >> N;
    List.reserve(N);
    for (int i = 0; i < N; i++) {
        std::string key;
        std::cin >> key;
        std::cout << insertSortedList(List, i, key) << std::endl;
    }

    return 0;
}

网上执行通过的代码链接

思路

1、 从小到大排序；

2、二分法查找插入；

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int max_len = 100;
static int insertSortedList(char **List, int size, char *key)
{
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int ret = strcmp(List[mid], key);
        if (ret < 0) // List[mid] < new_word
            left = mid + 1;
        else // List[mid] >= new_word
            right = mid - 1;
    }
 
    for(int i = size; i > left; i--)
        List[i] = List[i - 1];
 
    List[left] = key;
    return left;
}
 
int main()
{
    int N;
    char **List;
    scanf("%d", &N);
    List = (char **)malloc(N * sizeof(char *));
    for(int i = 0; i < N; i++){
        char *key = (char *)malloc(max_len * sizeof(char));
        scanf("%s", key);
        printf("%d\n", insertSortedList(List, i, key));
        key = NULL;
    }
 
    //for(int i = 0; i < N; i++)
    //    free(List[i]);
    free(List);
    return 0;
}