[问题解决,谢谢回答]我有一个排序的向量v
和一个向量num
,这是我如何删除向量v
中的元素:
vector <int> v;
vector <int> num;
//gets input
//for an example: v = {1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 6}
//num.size() = 0
num.push_back(v[v.size()-1]); //adds num "v"'s maximum element
v.erase(v.begin()+v.size()-1); // removes that element
while(v.size() > 0) {
num.push_back(v.back()); //adds num "v"'s maximum element
v.erase(v.begin()+v.size()-1); // removes that element
for(int i = 0; i < num.size()-1; i++) // checkes all elements of num except the last one added
{
int ggcd = __gcd(num[num.size()-1], num[i]);
int fnd = findv(v, ggcd); // finds GCD of maximum element and element i of num
v.erase(v.begin()+fnd); // removes
fnd = findv(v, ggcd); //repeats one more time
v.erase(v.begin()+fnd);
}
}
其中,函数findv(vector<int> v, int x)
是通过二分搜索找到不小于x
的最小元素的索引的函数:
int findv(const vector<int>& v, int x) // simply, finds
{
int l = 0, r = sz(v), mid;
while(r-l > 1)
{
mid = (l+r)/2;
if(v[mid] < x) l = mid;
else if(v[mid] > x) r = mid;
else return mid;
}
return l;
}
开始时向量v的大小总是某个n的平方(这里是4),所以向量大小在中间永远不会达到0。运行时错误来自for
中的v.erase(v.begin()+fnd)
,因为当我删除它们时,没有运行时错误,并且在while/for之前的v.erase(v.begin()+v.size()-1)
可以完美地工作
在我发现问题是关于for中的擦除之后,我用v.erase(v.begin()+0)
替换了它们,看看问题是否在函数findv中。但这也给了我一个运行时错误,我用许多其他数字,大小-1和所有东西替换了它,但仍然,有一个运行时错误。我在互联网上搜索了很多,甚至试图改变我如何删除元素从v,但他们有其他错误/没有做我想要的。例如:
v.erase(remove(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i])), v.end());
按值删除,但它删除该值的所有元素,这不是我想要的。试着这样做:
vector<int>::iterator it = find(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i]));
int index = distance(v.begin(), it);
v.erase(v.begin()+index);
it = find(v.begin(), v.end(), __gcd(num[sz(num)-1], num[i]));
index = distance(v.begin(), it);
v.erase(v.begin()+index);
但是这个也给了我一个运行时错误。元素dontrun out while在while中导致n^2 + 2*n + 1 =(n+1)^2,对于另一个n,这是n^2。它可以用数学归纳法证明。顺便说一句,如果你想知道我在代码中到底做了什么,这是这个问题的解决方案:https://codeforces.com/problemset/problem/582/A,这是我的代码的完整版本:https://ideone.com/suu0GG
1条答案
按热度按时间qlfbtfca1#
我并没有确切地发现我的代码中到底有什么错误,但是,似乎我的问题不是关于擦除部分和其他事情是错误的。我不知道为什么删除擦除部分后没有运行时,也许是编译器错误。这些是我改变的东西,使它工作:
还有一个用户问我为什么我使用一个手工制作的函数'findv',而lowerband和upperband存在,这对我的代码来说是一个有效的问题。(我有理由这么说,但我只是笼统地这么说)