原创 【转】vector,deque与sort的用法比较及入门

#include <stdio.h>
// sort的定义
#include <algorithm>
// vector的定义
#include <vector>
// deque的定义
#include <deque>
// 同样，引入std命名空间
using namespace std;
// 用数组保存
int friends[1000];
// 用vector保存
vector<int> vtFriends;
// 用deque保存
deque<int> dqFriends;

int main()
{
int T;
scanf("%d", &T);
int iCase;
for (iCase = 1; iCase <= T; iCase++)
{
// 每次要将vector和deque请空
vtFriends.clear();
dqFriends.clear();
printf("Scenario #%d: ", iCase);
int n, f, tn;
scanf("%d%d", &n, &f);
// 由于后面要找三次，所以先把n的值保存下来
tn = n;
int i;
for (i = 0; i < f; i++)
{
// 保存到数组
scanf("%d", &friends);
// 保存到vector
vtFriends.push_back(friends);
// 保存到deque
dqFriends.push_back(friends);
}
// 排序，如果不给第三个参数，默认是按升序排
// sort实现的是快速排序，它是不稳定排序，
// 需要稳定排序时，用stable_sort，用法与sort完全一样
// 对数组进行排序
sort(friends, friends + f);
// 对vector进行排序
sort(vtFriends.begin(), vtFriends.end());
// 对deque进行排序
sort(dqFriends.begin(), dqFriends.end());
// 在数组里查找
for (i = f - 1; i >= 0; i--)
{
n -= friends;
if (n <= 0)
break;
}
// 在vector里查找
// 先恢复n的值
n = tn;
for (i = f - 1; i >= 0; i--)
{
n -= vtFriends.at(i);
if (n <= 0)
break;
}
// 在deque里查找
// 先恢复n的值
n = tn;
for (i = f - 1; i >= 0; i--)
{
// deque的at方法效率比vector低，
// 因为deque的元素在内存上不完全是连续的
n -= dqFriends.at(i);
if (n <= 0)
break;
}
if (i < 0)
puts("impossible");
else
printf("%d ", f - i);
puts("");
}
return 0;
}