hdu 2711

地址：http://acm.hdu.edu.cn/showproblem.php?pid=2711

题意：有n个牛排成一列，每个牛有序号(1~n)，给出每个牛之前有多少个序号小于当前牛的牛数，求序号。第一头牛的未给出。

mark：直接从后往前，每次找小于它但是没被选过的序号有多少个，暴力，效率是O(n^2)，200+ms。

正解应该是树状数组之类的，懒得写了。

代码：

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 int dp[8010], ans[8010], a[8010] ;
 6 int n ;
 7 
 8 int main ()
 9 {
10     int i, j, cnt  ;
11     while (~scanf ("%d", &n))
12     {
13         memset (dp, 0, sizeof(dp)) ;
14         for (i = 2 ; i <= n ; i++)
15             scanf ("%d", &a[i]) ;
16         for (i = n ; i >= 1 ; i--)
17         {
18             cnt = 0 ;
19             for (j = 1 ; dp[j]==1 || cnt < a[i];j++)
20                 if (dp[j]==0)cnt++ ;
21             ans[i] = j ;
22             dp[j] = 1 ;
23         }
24         for (i = 1 ; i <= n ; i++)
25             printf ("%d\n", ans[i]) ;
26     }
27     return 0 ;
28 }