链 - codechef

Question

我试图解决this问题，因为最后两天。我没有得到正确的结果。 接受的解决方案是先排序链的数量。我不明白他们为什么这样做。 只是第一个任务是正确的。对于第二项任务，答案是错误的，并且第三次超出限制。

这是我的代码：

#include<iostream> 
using namespace std; 
int main() { 
int t; 
cin>>t; 
while(t--) { 
    long n=0; 
    int f=0,c=0,cuts=0; 
    cin>>n>>c; 
    int toJoint=c-1; 
    int A[c]; 
    for (int i =0;i<c;i++) 
     cin>>A[i]; 
    if (c>2){ 
     for (int i =0;i<c;i++) { 
      if (A[i]==1) { 
       f++; 
       cuts++; 
       toJoint-=2; 
       if(toJoint<=1) break; 
      } 
     } 
     if (toJoint>0){ 
      if (f==0) cout<<toJoint<<endl; 
      else cout<<(cuts+toJoint)<<endl; 
     } 
     else cout<<cuts<<endl; 
    } 
    else if (c==1) cout<<0<<endl;  
    else cout<<++cuts<<endl; 
} 
return 0; 
} 

Answer 1

您有以下操作，其中的每一个可以被用于两个链连接在一起：

1. 切割链（> = 3）的中间（0更少链）
2. 切割链（> = 2）在端部（1支减链）
3. 剪下单个圆环（2支更少链）

的最佳解决方案从未需要使用（1），因此，目的是确保尽可能多的操作尽可能是（3）S，其余为（2）秒。做到这一点的最明显的方法是从最小的链条末端重复切下一个甜甜圈，并用它将最大的两个链条粘在一起。这是排序链的原因。即便如此，将长度变为堆也可能更快，并且只需要尽可能多地提取最小元素。

我们的问题是：你的算法只使用单甜甜圈操作（3），但不会尝试通过从最小链的末端切割甜甜圈，使更多的单一的甜甜圈。所以作为Jarod42指出，随着 反例，它是不是最佳的。

---

我还要指出的是，你的VLAS

int A[c]; 

的使用是一个非标准扩展。为了严格要求，您应该使用std::vector。

---

为了完整起见，这里有一个例子：

std::sort(A.begin(), A.end()); 

int smallest_index = 0; 
int cuts = 0; 

while (M > 1) 
{ 
    int smallest = A[smallest_index]; 
    if (smallest <= M - 2) 
    { 
     // Obliterate the smallest chain, using all its donuts to link other chains 
     smallest_index++; 
     M -= smallest + 1; 
     cuts += smallest; 
    } 
    else 
    { 
     // Cut M - 2 donuts from the smallest chain - linking the other chains into one. 
     // Now there are two chains, requiring one more cut to link 
     cuts += M - 1; 
     break; 
    } 
} 

return cuts; 

（免责声明：只对样本数据进行测试，在角落的情况下可能会失败或不工作）