top1编程
← 返回题目
题解

【入门】排队

3 条题解

  • 0
    @ 2026-7-29 0:06:28
    #include<bits/stdc++.h>
    using namespace std;
    // 定义变量 n 表示人数
    int n;
    // 定义数组 s 用于存储每个人的满意度,数组大小为 200005
    int s[200005];
    int main() {
        // 从标准输入读取人数 n
        cin>>n;
        // 循环读取每个人的满意度,并存储到数组 s 中
        for(int i=1; i<=n; i++) {
            cin>>s[i];
        }
        // 对数组 s 中的元素进行排序,从 s[1] 到 s[n],排序后数组元素从小到大排列
        sort(s+1,s+n+1);
        // 定义变量 res 用于存储最大的分数之和,初始化为 0
        long long res=0;
        // 定义变量 sum 用于存储当前排队接水的人的满意度之和,初始化为 0
        long long sum=0;
        // 从数组的最后一个元素开始向前遍历,即从满意度最大的人开始考虑
        for(int i=n; i>=1; i--) {
            // 将当前人的满意度累加到 sum 中
            sum+=s[i];
            // 如果当前排队接水的人的满意度之和小于等于 0,说明继续让后面的人接水会使总分数降低,停止循环
            if(sum<=0){
                break;
            } 
            // 将当前的满意度之和累加到 res 中,因为 sum 表示当前这一轮排队接水的人的总满意度,而这一轮接水结束时的分数就是 sum
            res+=sum;
        }
        // 输出最大的分数之和
        cout<<res;
        return 0;
    }
    
    • 0
      @ 2026-7-29 0:06:27
      #include <iostream> 
      using namespace std; 
      int n,m,m1; 
      int a[200005],pos[100005]; 
      int main(){
      	cin >> n >> m; 
      	for(int i=1; i<=n; i++){ 	
      		cin >> a[i]; 		
      		pos[a[i]]=i; //pos[编号]——存放位置		
      	} 	
      	for(int i=1; i<=m; i++){ 		
      		cin >> m1;//被叫到的编号 		
      		a[pos[m1]]=0; //原来的编号标记成0		
      		a[n+i]=m1; 	//把被叫编号移动到n+i位置	
      		pos[m1]=n+i;//把被叫编号更新成现在的位置 		
      	} 	
      	for(int i=1; i<=n+m; i++){ //总共n个人被叫m次	
      		if(a[i]==0) 	//跳过标记0的位置输出其他元素		
      			continue; 		
      		cout << a[i] << " "; 		
      	} 	
      	return 0; 	
      }
      
      
      /*
      	50分解法
      
      #include<bits/stdc++.h>
      using namespace std;
      int n, m;
      int a[1000005];
      int main(){
      	cin >> n >> m;
      	for (int i = 1; i <= n; i++) {
      		cin >> a[i];
      	}
      	while (m--) {
      		int t;
      		cin >> t;
      		for (int i = 1; i <= n; i++) {
      			if (a[i] == t) {
      				swap(a[i], a[++n]);
      				break;
      			}
      		}
      	}
      	for (int i = 1; i <= n; i++) {
      		if (a[i]) {
      			cout << a[i] << ' ';
      		}
      	}
      	return 0;
      }
      */
      
      • 0
        @ 2026-7-28 23:10:25
        #include <iostream> 
        using namespace std; 
        int n,m,x; 
        int a[200005],b[100005]; 
        int main(){
        	cin >> n >> m; 
        	for(int i=1; i<=n; i++){ 	
        		cin >> a[i]; 		
        		b[a[i]]=i; //b[编号]——存放a[i]的位置		
        	} 	
        	for(int i=1; i<=m; i++){ 		
        		cin >> x;//被叫到的编号 		
        		a[b[x]]=0; //原来的位置标记成0		
        		a[n+i]=x; 	//把被叫编号移动到n+i位置	
        		b[x]=n+i;//把被叫编号更新成现在的位置 		
        	} 	
        	for(int i=1; i<=n+m; i++){ //总共n个人被叫m次	
        		if(a[i]!=0) {	//跳过标记0的位置输出其他元素			
        			cout << a[i] << " "; 
        		}		
        	} 	
        	return 0; 	
        }
        
        • 1