2 solutions

  • 1
    @ 2024-9-3 13:17:39
    #include<bits/stdc++.h>
    using namespace std;
    int a[601];
    int main(){
    	int n,w;
    	cin>>n>>w;
    	for(int i=1;i<=n;i++){
    		int x;
    		cin>>x;
    		a[x]++;
    		int s=max(1,i*w/100);
    		int k=0;
    		for(int i=600;i>=0;i--){
    			k+=a[i];
    			if(k>=s){
    				cout<<i<<" ";
    				break;
    			}
    		}
    	}
    }
    
    • 0
      @ 2024-9-1 16:15:47

      一直sort会TLE!! 所以用桶排(因为“对于所有测试点,每个选手的成绩均为不超过600的非负整数”)

      #include<bits/stdc++.h>
      using namespace std;
      int arr[600];
      int main(){
          int n,m;
          scanf("%d%d",&n,&m);
          for(int i=1;i<=n;i++){
              int a;
              cin>>a;
              int mid=max(1,int(i*m/100));
              int cnt=0;
              arr[a]++;
              for(int j=600;j>=0;j--){
                  cnt+=arr[j];
                  if(cnt>=mid){
                      cout<<j<<' ';
                      break;
                  }
              }
          }
          return 0;
      }
      /*
      特别注意:
      在计算计划获奖人数时,如用浮点类型的变量
      (如 C/C++ 中的 float 、 double,Pascal 中的 real 、 double 、 extended 等)
      存储获奖比例 w%w%,则计算 5×60%5×60% 时的结果可能为 3.0000013.000001,
      也可能为 2.9999992.999999,向下取整后的结果不确定。因此,建议仅使用整型变量,以计算出准确值。
      所以建议i*w/100《-这样写(不然85WA)
      */
      
    • 1

    Information

    ID
    6253
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    2
    Tags
    # Submissions
    48
    Accepted
    17
    Uploaded By