Problem A. Standing Ovation
Problem's Link: https://code.google.com/codejam/contest/6224486/dashboard#s=p0
Mean:
题目说的是有许多观众，每个观众有一定的羞涩值，只有现场站起来鼓掌的人数达到该值才会站起来鼓掌，问最少添加多少羞涩值任意的人，才能使所有人都站起来鼓掌。
analyse:
贪心模拟一下，从前往后扫一遍就行。
Time complexity: O(n)
Source code:
#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int MAXN=1110; int n; char s[MAXN]; int main() { // freopen("E:\\Code_Fantasy\\C\\A-small-attempt0.txt","r",stdin); // freopen("E:\\Code_Fantasy\\C\\A-small-attempt1.txt","w",stdout); int t; scanf("%d",&t); for(int Cas=1;Cas<=t;++Cas) { scanf("%d",&n); scanf("%s",s); int ans=0; int shy=s[0]-'0'; for(int i=1;i<=n;++i) { if(s[i]-'0'!=0) { if(shy>=i) shy+=(s[i]-'0'); else { ans+=(i-shy); shy=i+(s[i]-'0'); } } } printf("Case #%d: %d",Cas,ans); if(Cas!=t) puts(""); } return 0; }
