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<<" ";
	}
}