1 solutions

  • 0
    @ 2024-9-6 20:20:12

    贪心的选择套题数量最少的,这里使用优先队列

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int main(){
    	priority_queue<int,vector<int>,greater<int> > pq1;//小根堆,优先队列 
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		int x;
    		cin>>x;
    		pq1.push(x);
    	}
    	int cnt=0;
    	for(int i=1;i<=n;i++){
    		priority_queue<int,vector<int>,greater<int> >pq2;//回收不达标(数量不足)的套题 
    		int u=pq1.size();
    		int w=pq2.size();
    		while(u--){//优先选数量少的 
    			int top=pq1.top();
    			if(top>=i){
    				cnt++; 
    				//cout<<top<<" ";
    				pq1.pop();//找到了,丢掉此套题 
    				break;
    			}
    
    
    
    			pq2.push(top);//回收 
    			pq1.pop();
    		}
    		while(w--){
    			pq1.push(pq2.top());//回收再利用 
    			pq2.pop();
    			
    		}
    	}
    	cout<<cnt;
    	return 0;
    }
    
    • 1

    Information

    ID
    9832
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    2
    Tags
    # Submissions
    3
    Accepted
    1
    Uploaded By