0 
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
using namespace std;
void safe(int n,int k,int a[])
{
    vector<int>s(a+0,a+n);
    vector<int>b(a+0,a+n);
    while(s.size()>1)
    {
        int r;
        r=s.size();
       int count=1;
        while(count<=r)
        {
            b[count%r]=0;
            count=count+k;
        }
    b.erase(remove(b.begin(),b.end(),0),b.end());
    s=b;    
    }
    
    for(int x:s)
    {
        cout<<x<<"\n";
    }
}


int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,k;
        cin>>n>>k;
        int *a=new int[n];
        for(int j=1;j<=n;j++)
        {
            a[j-1]=j;
        }
        if(n>2)
        {
        safe(n,k,a);
        }
        else if(n==2)
        {
     cout<<a[1]<<"\n";
        }
        else
        cout<<a[0]<<"\n";
    }
}

输入：

4
4 2
5 2
2 1
50 10

输出：

1
3
2
19  --> it should be 36

如果你不知道这个问题 问题描述：有n个人围成一圈（顺时针从1到n编号）等待被处决。计数从圆圈中的点 1 开始，并沿固定方向（顺时针）围绕圆圈进行。在每个步骤中，都会跳过一定数量的人并执行下一个人。消除围绕圆圈进行（随着被处决的人被移除，圆圈变得越来越小），直到只剩下最后一个人，他被赋予了自由。给定总人数 n 和数字 k，表示跳过 k-1 人，循环杀死第 k 人。任务是选择初始圈子中的位置，以便您是最后一个并生存下来。考虑如果 n = 5 且 k = 2，则安全位置为 3。首先，位置2的人被杀，然后位置4的人被杀，然后位置1的人被杀。最后，位置 5 的人被杀死。所以位置 3 的人活了下来。

4

1 回答 1

1

这是一个可能的解决方案，希望评论说清楚。无需分配 anint[]并将其复制到向量中，您可以直接使用iota. 同样，您可以随时删除元素，而不是在后面的步骤中归零和删除。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;
void safe(int n, int k) {
  vector<int> s(n);
  // Init the vector 1..n
  iota(s.begin(), s.end(), 1);
  int i = 0;
  // While more than one survive...
  while (s.size() > 1) {
    // Skip forward (k-1)
    i = (i + k - 1) % s.size();
    // Kill the next one
    s.erase(s.begin() + i);
  }
  for (int x : s) {
    cout << x << "\n";
  }
}

int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int n, k;
    cin >> n >> k;
    if (n > 2) {
      safe(n, k);
    } else if (n == 2) {
      cout << 2 << "\n";
    } else
      cout << 1 << "\n";
  }
}
于 2020-12-03T20:55:01.130 回答