百度第二题谁啊帮我看看
一开始用STL排序,提示超内存;
然后自己写冒泡排序,提示超时间;
然后自己写堆排,还是超时;
然后用multiset,依旧超时
#百度##笔试题目##include "stdafx.h"
#include <string>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <bitset>
#include <stack>
using namespace std;
int cmp(pair<int, int> p1, pair<int, int> p2)
{
if (p1.second < p2.second)
return 1;
else if (p1.second == p2.second && p1.first <= p2.first)
return 1;
else
return 0;
}
struct Cmp {
bool operator()(const pair<int, int> &p1, const pair<int, int> &p2)
{
if (p1.second < p2.second)
return 1;
else if (p1.second == p2.second && p1.first <= p2.first)
return 1;
else
return 0;
}
};
void Adjust(vector<pair<int, int>> vecPairs, int a, int b)
{
int nL = 2 * a + 1;
int nR = 2 * a + 2;
int nM = a;
if (nL < b && cmp(vecPairs[nL],vecPairs[nM]) == 0)
{
nM = nL;
}
if (nR < b && cmp(vecPairs[nL], vecPairs[nM]) == 0)
{
nM = nR;
}
if (a != nM)
{
swap(vecPairs[nM], vecPairs[a]);
Adjust(vecPairs, nM, b);
}
}
void Sort(vector<pair<int, int>> vecPairs)
{
for (int nindex = vecPairs.size() / 2 - 1; nindex >= 0; --nindex)
{
Adjust(vecPairs, nindex, vecPairs.size());
}
for (int nindex = vecPairs.size() - 1; nindex >= 0; nindex--)
{
swap(vecPairs[0], vecPairs[nindex]);
Adjust(vecPairs, 0, nindex);
}
return;
}
int main()
{
int nNum;
int nN;
cin >> nNum >> nN;
while (nNum--)
{
int nTime = 0;
vector<pair<int, int>> vecPairs;
//multiset<pair<int, int>, Cmp> setPairs;
int nTem1, nTem2;
while (nN--)
{
cin >> nTem1 >> nTem2;
vecPairs.push_back(make_pair(nTem1, nTem2));
//setPairs.insert(make_pair(nTem1, nTem2));
}
//sort(vecPairs.begin(),vecPairs.end(),cmp);
Sort(vecPairs);//重新写堆排
for (auto i : vecPairs)
{
nTime += i.first;
if (nTime > i.second)
{
cout << "No" << endl;
break;
}
}
cout << "Yes" << endl;
}
system("pause");
return 0;
}
OPPO公司福利 1112人发布