Counting Sort 3 (计数排序 3)

In the previous challenge, it was easy to print all the integers in order, since you did not have to access the original list. Once you had obtained the frequencies of all the integers, you could simply print each integer in order the correct number of times. However, if there is other data associated with an element, you will have to access the original element itself.

In the final counting sort challenge, you are required to print the data associated with each integer. This means, you will go through the original array to get the data, and then use some “helper arrays” to determine where to place everything in a sorted array.

If you know the frequencies of each element, you know how many times to place it, but which index will you start placing it from? It will be helpful to create a helper array for the “starting values” of each element.
在前面的任务里，将列表中的整数按序输出是很简单的，因为你不需要访问原列表。一旦你获得了所有整数的出现频率，你就可以简单地按序打印每个整数的次数。但是，如果有其他数据跟每个元素有关联，那么你就必须访问原来的元素本身了。

在最后这个任务里，你被要求打印与整数关联的数据。这意味着你需要回到原列表取获取数据，并且使用一些“辅助数组”来确定在哪里将所有数据按序存放。

如果你知道每个元素的出现频率，你知道这样的元素需要存储多少次，但是，从哪个位置开始存储呢？所以在这里建立一个辅助数组储存每个元素的“起始位置”将会非常有帮助。

Challenge （任务）

You will be given a list that contains both integers and strings. In this challenge you just care about the integers. For every value i from 0 to 99, can you output L, the number of elements that are less than or equal to i?
给你一个列表，包含整数和字符串。本任务你只需关注整数。对于每个整数i，能否输出小于等于i的数的个数L？

Input Format （输入格式）

• n, the size of the list ar.
• n lines follow, each containing an integer x and a string s.
• 列表大小n
• 接下来n行，每行一个整数x和一个字符串s

  Output Format （输出格式）

  Output L for all numbers from 0 to 99 (inclusive).
  输出0～99这些数的L

  Constraints （约束条件）

  100<=n<=10^6
  0<=x<100
  length of string<=10

Sample Input（样例输入）

10
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the

Sample Output（样例输出）

1 3 5 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

Explanation （解释）

0 appears 1 time, so the 0th number is 1.
0 and 1 combined appear 3 times, so the next number is 3.
This continues for the rest of the list, until no more new numbers appear.
0出现1次，所以小于等于1的有1个，0和1共出现3次，所以小于等于2的有3个…

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int a[100];
int main() {
    int n;
    cin>>n;
    for(int i=0,val;i<n;i++){
        string str;
        cin>>val>>str;
        a[val]++;
    }
    int s=0;
    for(int val=0;val<100;val++){
        s+=a[val];
        cout<<s<<" ";
    }
    return 0;
}

总结

同样基于后续任务及题目中提及的辅助数组概念，将程序调整如下，生成辅助数组L然后输出

int a[100],L[100];
int main() {
    int n;
    cin>>n;
    for(int i=0,val;i<n;i++){
        string str;
        cin>>val>>str;
        a[val]++;
    }
    int s=0;
    for(int val=0;val<100;val++){
        s+=a[val];
        L[val]=s;
        cout<<s<<" ";
    }
    return 0;
}