約瑟夫問題

題目連結

子任務1

• 要如何決定每次要刪掉的是誰?
  暴力實作
  每次都O(N)移動到下一個需要被踢出的人身上，再使用O(N)的方法將這個人踢出，總共需要 N 次，因此時間複雜度是 O(N^2)。
  //其實子任務1出爛了。

  #include<bits/stdc++.h>
  using namespace std;
  #define int long long
  signed main() {
      int n, k;
      cin>>n>>k;
      int now=0;
      vector<int> v(n, 0);
      for(int i=0;i<n;i++) v[i]=i;
      for(int i=1;i<n;i++) {
          int l=v.size();
          for(int j=1;j<k;j++) {
              now++;
              now%=l;
          }
          v.erase(v.begin()+now);
      }
      cout<<v[0];
  }
  // 其實這個也可以過子任務二

子任務二

跟句子任務1的程式我們可以發現

for(int j=1;j<k;j++) {
            now++;
            now%=l;
}

其實就是

now=(now+k-1)%l;

因此我們可以把這邊簡化成O(1)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n, k;
    cin>>n>>k;
    int now=0;
    vector<int> v(n, 0);
    for(int i=0;i<n;i++) v[i]=i;
    for(int i=1;i<n;i++) {
        int l=v.size();
        now=(now+k-1)%l;
        v.erase(v.begin()+now);
    }
    cout<<v[0];
}

子任務三

由於子任務一二的提示，我們可以發現無論k是多少其實不影響時間複雜度，以及一定要做n-1次操作，所以剩下的優化便只剩下把人踢出這個過程，透過平板電視，可以把這個優化到O(logn)。

其實也可以Treap。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define flightzz ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int n, k;
signed main() {
    cin>>n>>k;
    ordered_set x;
    for(int i=0;i<n;i++) {
        x.insert(i);
    }
    int key=0;
    for(int i=0;i<n;i++) {
        key=(key+k-1)%x.size();
        auto it=x.find_by_order(key);
        
        if(i==n-1) cout<<*it<<" ";
        x.erase(it);
    }
}       

子任務四

由於N很大，時間複雜度不是O(N)就是O(1)。
詳細請見 : https://hackmd.io/@erichung0906/H1ljCesy_

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define flightzz ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
int n, k;
int ans() {
    int ret=0;
    for(int i=2;i<=n;i++) {
        ret=(ret+k)%i;
    }
    return ret;
}
signed main() {
    cin>>n>>k;
    // ordered_set x;
    // for(int i=0;i<n;i++) {
    //     x.insert(i);
    // }
    // int key=0;
    // for(int i=0;i<n;i++) {
    //     key=(key+k-1)%x.size();
    //     auto it=x.find_by_order(key);
        
    //     if(i==n-1) cout<<*it<<" ";
    //     x.erase(it);
    // }
    cout<<ans();
}