Java实现蓝桥杯算法训练 Beaver's Calculator

清疚 2023-07-25 09:42 17阅读 0赞

## 试题 算法训练 Beaver’s Calculator ##

问题描述  
　　从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为"Beaver’s Calculator 1.0"。它非常特别，并且被计划使用在各种各样的科学问题中。  
　　为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了 ki个计算题。第i个科学家带来的问题编号1到n，并且它们必须按照编号一个一个计算，因为对于每个问题的计算都必须依赖前一个问题的计算结果。  
　　每个教授的每个问题都用一个数 ai, j  来描述，i（1≤i≤n）是科学家的编号，j（1≤j≤ ki ）是问题的编号， ai, j  表示解决这个问题所需资源单位的数量。  
　　这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，计算器分配或解放资源。  
　　计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而言，每一个接下来的问题所需的资源不少于前一个，是非常重要的。  
　　给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得“坏对”尽可能少。  
　　所谓“坏对”，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个科学家给出的问题，计算它们的相对顺序必须是固定的。  
输入格式  
　　第一行包含一个整数n，表示科学家的人数。接下来n行每行有5个整数，ki, ai, 1, xi, yi, mi (0 ≤ ai, 1 < mi ≤ 109, 1 ≤ xi, yi ≤ 109) ，分别表示第i个科学家的问题个数，第1个问题所需资源单位数，以及3个用来计算 ai, j 的参量。ai, j = (ai, j - 1 \* xi + yi)mod mi。  
输出格式  
　　第一行输出一个整数，表示最优顺序下最少的“坏对”个数。  
　　如果问题的总个数不超过200000,接下来输出 行，表示解决问题的最优顺序。每一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。  
样例输入  
2  
2 1 1 1 10  
2 3 1 1 10  
样例输出  
0  
1 1  
2 1  
3 2  
4 2  
数据规模和约定  
　　20%的数据 n = 2, 1 ≤ ki ≤ 2000；  
　　另外30%的数据 n = 2, 1 ≤ ki ≤ 200000；  
　　剩下50%的数据 1 ≤ n ≤ 5000, 1 ≤ ki ≤ 5000。

import java.io.*;
    
    class Expert{ 
    	int indexOfProblem;
    	int numOfProblem;
    	long[] problem;  // 存放每个问题所消耗的资源数
    }
    
    public class Main{ 
    	static Expert[] experts;
    	
    	public static void merge(int start,int end,long[][] ans) { 
    		int mid = (start+end)>>1;
    		int i = start;
    		int j = mid+1;
    		int k = 0;
    		long[][] temp = new long[end-start+1][2];
    
    		while(i <= mid && j <= end) { 
    			if(ans[i][0] > ans[j][0]) { 
    				temp[k][0] = ans[j][0];
    				temp[k++][1] = ans[j++][1];
    			}else { 
    				temp[k][0] = ans[i][0];
    				temp[k++][1] = ans[i++][1];
    			}
    		}
    		
    		while(i <= mid) { 
    			temp[k][0] = ans[i][0];
    			temp[k++][1] = ans[i++][1];
    		}
    
    		while(j <= end) { 
    			temp[k][0] = ans[j][0];
    			temp[k++][1] = ans[j++][1];
    		}
    
    		for( i = 0 ; i < k; i++) { 
    			ans[i+start][0] = temp[i][0];
    			ans[i+start][1] = temp[i][1]; 
    		}
    	}
    	
    	public static void mergeSort(int start,int end, long[][] ans) { 
    
    		if(start < end) { 
    			int mid = (start + end)>>1;
    			mergeSort(start, mid, ans);
    			mergeSort(mid+1, end, ans);
    			merge(start, end, ans);
    		}
    	}
    	
    	public static void main(String[] args) throws IOException{ 
    		
    		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    		
    		in.nextToken();
    		int n = (int)in.nval;
    		long numOfAllProblems = 0;
    		long maxBad = -1;
    		experts = new Expert[n];
    		for(int i = 0 ; i < n ; i++) { 
    			experts[i] = new Expert();
    		}
    		for(int i = 0 ; i < n; i++) { 
    			long oneBad = 0;
    			in.nextToken();
    			experts[i].numOfProblem = (int)in.nval;
    			numOfAllProblems += (int)in.nval;
    			experts[i].problem = new long[(int)in.nval+1];
    			experts[i].problem[0] = -1;
    			experts[i].indexOfProblem = 1;
    			long firstProblem, xi, yi, mi;
    			in.nextToken();
    			firstProblem = (long)in.nval;
    			in.nextToken();
    			xi = (long)in.nval;
    			in.nextToken();
    			yi = (long)in.nval;
    			in.nextToken();
    			mi = (long)in.nval;
    			experts[i].problem[1] = firstProblem;
    			for(int j = 2 ; j <= experts[i].numOfProblem ; j++) { 
    				experts[i].problem[j] = (experts[i].problem[j-1] * xi + yi) % mi; 
    				if(experts[i].problem[j] < experts[i].problem[j-1]) { 
    					oneBad++;
    				}
    			}
    			if(oneBad > maxBad) { 
    				maxBad = oneBad;
    			}
    		}
    		
    		out.println(maxBad);
    		out.flush();
    		if(numOfAllProblems <= 200000) { 
    			long[][] ans = new long[(int) numOfAllProblems][2];
    			int start = 0, end = 0;
    			
    			while(end < numOfAllProblems) { 
    				for(int i = 0 ; i < n; i++) { 
    					int j;
    					for(j = experts[i].indexOfProblem ; j <= experts[i].numOfProblem; j++) { 
    						if(j != experts[i].indexOfProblem && (experts[i].problem[j] < experts[i].problem[j-1])) { 
    							experts[i].indexOfProblem = j;
    							break;
    						}
    						ans[end][1] = i;
    						ans[end++][0] = experts[i].problem[j];
    					}
    					if(j > experts[i].numOfProblem) { 
    						experts[i].indexOfProblem = j;
    					}
    				}
    				
    				mergeSort(start, end-1, ans);
    				
    				start = end;
    			}
    			
    			for(int i = 0 ; i < numOfAllProblems; i++) { 
    				out.println(ans[i][0] + " " + (ans[i][1]+1));
    				out.flush();
    			}
    
    		}
    	}
    }