Codechef MasterChef 中的错误答案
Wrong answer in Codechef MasterChef
我在解决问题时遇到问题http://www.codechef.com/problems/MCHEF , here is my solution http://ideone.com/SsbABr
我已经使用 knapsack 和 set 解决了这个问题，但是我得到了错误的答案，似乎无法弄清楚为什么！我也看过同样的社论，它也是这样做的。我相信我的背包 DP 代码是正确的。
问题似乎出在下面的部分，它使用 set 来插入和维护间隔成本，这样我就可以获得每个元素的最低成本。
vector<int> L[n],R[n];
vector<oper> operarray;
vector<int> cost;
for(int i=0;i<m;i++){
int j,k,val;
cin >> j >> k >> val;
L[j-1].push_back(i);
R[k-1].push_back(i);
cost.push_back(val);
}
set<pair<int,int> > iset;
for(int i=0;i<n;i++){
for(int j=0;j<L[i].size();j++){
int index = L[i][j];
iset.insert(make_pair(cost[index],index));
}
b[i] = iset.begin()->first;
for(int j=0;j<R[i].size();j++){
int index = R[i][j];
iset.erase(make_pair(cost[index],index));
}
实际上，问题是我没有检查集合是否为空，并且当我将空集合的开始元素分配给行中的数组元素时，编译器没有提示任何 运行 时间错误
b[i] = iset.begin()->first;
上面应该改成
if(!iset.empty())
b[i] = iset.begin()->first;
我在解决问题时遇到问题http://www.codechef.com/problems/MCHEF , here is my solution http://ideone.com/SsbABr
我已经使用 knapsack 和 set 解决了这个问题，但是我得到了错误的答案，似乎无法弄清楚为什么！我也看过同样的社论，它也是这样做的。我相信我的背包 DP 代码是正确的。
问题似乎出在下面的部分，它使用 set 来插入和维护间隔成本，这样我就可以获得每个元素的最低成本。
vector<int> L[n],R[n];
vector<oper> operarray;
vector<int> cost;
for(int i=0;i<m;i++){
int j,k,val;
cin >> j >> k >> val;
L[j-1].push_back(i);
R[k-1].push_back(i);
cost.push_back(val);
}
set<pair<int,int> > iset;
for(int i=0;i<n;i++){
for(int j=0;j<L[i].size();j++){
int index = L[i][j];
iset.insert(make_pair(cost[index],index));
}
b[i] = iset.begin()->first;
for(int j=0;j<R[i].size();j++){
int index = R[i][j];
iset.erase(make_pair(cost[index],index));
}
实际上，问题是我没有检查集合是否为空，并且当我将空集合的开始元素分配给行中的数组元素时，编译器没有提示任何 运行 时间错误
b[i] = iset.begin()->first;
上面应该改成
if(!iset.empty())
b[i] = iset.begin()->first;