CodeForces - 876D Sorting the Coins 模拟+思維

http://codeforces.com/contest/876/problem/D

題意：每次執行算法：①每次都是從左向右看，②看到第i個時，如果他是非法的且第i+1是非法的就交換這兩個，③最開始先看一遍不做交換。求最後沒有可以交換了，需要執行算法幾次。現在每次往裡面放一個非法的硬币，求每次需要執行上述算法幾次(第一次什麼都不放)。

題解：其實寫幾個就可以發現，每執行一次算法，非法硬币就有一個會歸位到末尾且不再移動。是以每次統計出有幾個硬币沒有歸位即可，具體看代碼了解。

代碼：

#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define d(a) cout<<a<<endl
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 300000 + 5;
const int mod = 1000000000 + 7;
const double eps = 1e-8;

bool vis[N];
int ans[N];

int main(){
	int n,x,num,last;
	cin>>n;
	last=n,num=0;
	for(int i=1;i<=n;i++){
		cin>>x;
		vis[x]=1;
		num++;
		while(vis[last]){
			last--;
			num--;
		}
		ans[i]=num;
	}
	for(int i=0;i<=n;i++){
		cout<<ans[i]+1<<" ";
	}
}