复习vector —— 原题链接
题目描述
给定N个数组，要求先对这N个数组分别进行排序，然后再根据N的数组的字典序对这N个数组进行排序。输出排序的结果。
输入
第一行一个整数N，表示数组数。
接下来N（N≤1000）行，每一行先包含一个整数C（C≤1000），表示数组的大小，接下来C个整数，表示数组中的一个元素。
输出
共N行，每行表示一个数组。
样例输入
4
1 3
1 1
2 2 1
3 2 3 1
AC代码：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
vector<int> a[N];//理解为一个二维数组,数组的每一行都是一个vector
int main()
{
int T; cin >> T; //T组数据
for (int i = 0;i < T;i++)
{
int n; cin >> n;//n表示每个vector中元素的个数
for (int j = 0;j < n;j++)
{
int x; cin >> x;
a[i].push_back(x);
}
}
for (int i = 0;i < T;i++) sort(a[i].begin(),a[i].end());
/* 第1次sort之后,各行的vector如下:
a[0]:3
a[1]:1
a[2]:1 2
a[3]:1 2 3
*/
sort(a,a + T);
/* 第2次sort之后,各行的vector如下:
1
1 2
1 2 3
3
*/
vector<int>::iterator it;
for (int i = 0;i < T;i++)
{
for (it = a[i].begin();it != a[i].end();it++)
{
cout << *it << " ";
}
cout << endl;
}
return 0;
}
例2 约瑟夫问题
题目描述
约瑟夫问题来源于公元1世纪的犹太历史学家Josephus。问题描述，有n个人（分别以编号1，2，3…n表示）围成一个圆圈，从编号为1的人开始进行1～m正向报数，报到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；如此重复下去，直到所有的人全部出列，求最后一个出列人的编号
输入
输入文件仅有一行包含二个用空格隔开的整数N，M （2≤N≤100000，M≤10^9）
输出
输出文件仅有一行包含一个整数表示一个整数，表示最后一个人在队列中的编号。
样例输入
8 3
样例输出
7
AC代码：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,m; cin >> n >> m;
vector<int> v;
for (int i = 1;i <= n;i++) v.push_back(i);
int c = -1;
while (v.size() != 1)
{
c = (c + m) % v.size();
v.erase(v.begin() + c);
c--;
}
cout << v[0] << endl;
return 0;
}
