#c
#c
Вопрос:
Недавно я пишу c , решая проблемы с онлайн-судьей. При сортировке сбрасывается ядро. Это кажется таким странным. Независимо от того, когда код будет принят онлайн-судьей, я озадачен, почему могло быть сброшено ядро, я использовал std::sort много раз.
Ниже приведен код.
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Pair {
Pair(int xx, int yy) : x(xx), y(yy) {}
int x;
int y;
};
int get_min(int a, int b) {
return (a <= b) ? a : b;
}
bool pool_compare(const Pairamp; a, const Pairamp; b) {
return a.x a.y <= b.x b.y;
}
void get_boundary(const vector<int>amp; nums1, const vector<int>amp; nums2,
const int k, intamp; p, intamp; q) {
q = 0;
p = 0;
int tail = get_min(k, nums1.size() nums2.size());
int cnt = 1;
while (cnt < tail) {
if (q 1 >= nums2.size() ||
nums1[p 1] nums2[q] <= nums1[p] nums2[q 1]) {
p ;
}
else {
q ;
}
if (p * q >= k) {
break;
}
cnt ;
}
}
vector<pair<int, int> > kSmallestPairs(vector<int>amp; nums1, vector<int>amp; nums2, int k) {
vector<pair<int, int> > ret;
if (0 == k) {
return ret;
}
int p = 0;
int q = 0;
get_boundary(nums1, nums2, k, p, q);
vector<Pair> pool;
for (int i = 0; i <= p; i ) {
for (int j = 0; j <= q; j ) {
pool.push_back(Pair(nums1[i], nums2[j]));
}
}
std::sort(pool.begin(), pool.end(), pool_compare);
k = get_min(pool.size(), k);
for (int i = 0; i < k; i ) {
ret.push_back(pair<int, int>(pool[i].x, pool[i].y));
}
return ret;
}
int main() {
int a[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
vector<int> nums1(a, a sizeof(a) / sizeof(int));
int b[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
vector<int> nums2(b, b sizeof(b) / sizeof(int));
vector<pair<int, int> > r = kSmallestPairs(nums1, nums2, 1000);
for (size_t i = 0; i < r.size(); i ) {
printf("%dt%dn", r[i].first, r[i].second);
}
return 0;
}
Стек вызовов указан ниже, похоже, он не очень помогает.
#0 0x0000000000400900 in pool_compare(Pair constamp;, Pair constamp;) ()
#1 0x00000000004025c3 in __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > > std::__unguarded_partition<__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, Pair, bool (*)(Pair constamp;, Pair constamp;)>(__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, Pair, bool (*)(Pair constamp;, Pair constamp;)) ()
#2 0x0000000000401ac2 in void std::__introsort_loop<__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, long, bool (*)(Pair constamp;, Pair constamp;)>(__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, long, bool (*)(Pair constamp;, Pair constamp;)) ()
#3 0x00000000004011b3 in void std::sort<__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, bool (*)(Pair constamp;, Pair constamp;)>(__gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, __gnu_cxx::__normal_iterator<Pair*, std::vector<Pair, std::allocator<Pair> > >, bool (*)(Pair constamp;, Pair constamp;)) ()
#4 0x0000000000400b9e in kSmallestPairs(std::vector<int, std::allocator<int> >amp;, std::vector<int, std::allocator<int> >amp;, int) ()
#5 0x0000000000400dbb in main ()
Ответ №1:
Ваш компаратор разрывает контракт. Предполагается, что он соответствует строгому отношению слабого упорядочения.
Это означает, что он должен давать false результат при передаче идентичных элементов, и cmp(a,b) и cmp(b,a) никогда не будет давать true оба раза для одного и того же a и b
Эмпирическое правило: не используйте <= для компараторов; используйте < вместо этого.