QwQ为数不多的几次有部分分的OI赛制的SRM，感谢CCZ的一屋子部分分= =

 

A. 模拟只会猜题意

 

B. 贪心只能过样例

给出n个数a[i]（1<=a[i]<=n），问最多能把这些数分成几组，使得每个数a[i]所在的组至少有a[i]个数

输入格式

第一行一个整数n，接下来n行每行一个整数分别是a[1],a[2],...,a[n]

输出格式

一行，输出答案，一个整数

分析

因为是按组分，所以顺序也就不重要了，先sort成递增

为了保证分组数最多，应该从大到小一个个满足（有点像弹飞绵羊呢）

方程为DP[i] = max( DP[i-arr[i]]+1 , DP[i-1] )

注意边界问题！

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #define LL long long 5 using namespace std; 6  7 LL n; 8 LL DP[10000000]; 9 LL maxx[10000000];10 LL arr[10000000];11 12 int main(){13     scanf("%lld",&n);14     15     for(LL i = 1;i <= n;i++){16         scanf("%lld",&arr[i]);    17     }18     19     sort(arr+1,arr+1+n);20     21     for(LL i = 1;i <= n;i++){22         if(i-arr[i] < 0 || !i) maxx[i] = 0;23         else{24             25             maxx[i] = maxx[i-arr[i]]+1;26             27             if(i < n) maxx[i] = max(maxx[i],maxx[i-1]);28         }29     }30     31     printf("%lld",maxx[n]);32     33     return 0;34 }
        
       
      

 

C. 数学上来先打表

 

D. DP只会找规律