codves1282 约瑟夫问题

STL LIST 链表 暴力模拟 但是会 T list

听说正解是线段树

分析一下，我们有以下两种操作：

1． 找到剩余队列中第K个人在数组中的位置

2． 删除第K个人

假如我们一开始给每个人一个权值1，然后维护一个前缀和s(n)那么，操作1就变成了找到前缀和为i的位置。当将第i个人删除时，只需将其权值置0，维护好前缀和，这样剩余队列中第i’个人的实际位置就在原先第i人后面了。

我们可以把前缀和转换为区间和，所以我们可以用线段树进行快速操作

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 using namespace std ; 11 12 int n,k ; 13 list
              
                a ; 14 list
               
                 ::iterator it ; 15 list
                
                  ::iterator temp ; 16 17 int main() 18 {19 scanf("%d%d",&n,&k) ; 20 for(int i=1;i<=n;i++) 21 a.push_back( i ) ; 22 it = a.begin() ;23 for(int i=1;i<=n;i++) 24 {25 for(int j=1;j