蓝桥杯刷题第七天

       这道题一开始看真的有点简单，但一开始跟着案例先入为主了，误以为是只有两个项目想着穷举完n个人，（n+1）*（n+2）/2种情况但后面发现项目不止两个，用链表来好像我也不会，用二维矩阵好像也表示不完，然后想了一会就想到了贪心，项目按照每个人依次来选项目，所以最多是两层循环n（人）*m（项目）的复杂度，用一个变量记录项目多一个人的涨幅，每轮循环中涨幅最多的就把这个人安排在这个项目，当遍历完n个人即可获得最优解。

下面是我的解法由于没有优化以及剪枝，所以只过了一半以上案例，其余都超时了，明天得看看官方解法来进行学习，整理成自己的思路来重新敲。

ps：但敲得过程中我发现，得先在草稿纸上理清思路再敲不然边敲边想会很容易走神，发呆。（明天试试）

import java.util.*;
public class Main {
	public static void main(String []args) {
		Scanner a = new Scanner(System.in);
		int num = a.nextInt();
		int n = a.nextInt();
		int []b = new int[n+1]; //每个项目的B值
		int []k = new int[n+1]; //每个项目的K值
		int []nu = new int[n+1];//每个项目有多少人玩
		int []z = new int[n+1];//每个项目最高能花多少钱
		int max =0;//最多赚多少钱
		for(int i=1;i<=n;i++) {
			k[i] = a.nextInt();
			b[i] = a.nextInt();
			nu[i] = 0;
		}
		int flag1 ;//门票钱
		int flag;//每轮比上一轮多的钱(涨幅)
		boolean tap;
		for(int j=1;j<=num;j++) {
			//num个人每个人参加哪个项目（贪心）
			int max1 = 0;//涨幅
			int xiabiao =1;
			tap =false;
			for(int i =1;i<=n;i++) {
				nu[i]++;
				if(b[i]+k[i]*nu[i]<=0) {
					nu[i]--;//亏得钱
					continue;//这个项目不用再加入人了
				}
				else {
					flag1 = (b[i]+k[i]*nu[i]);//这个项目的门票
                    flag = flag1*nu[i]-(flag1-k[i])*(nu[i]-1);
					if(max1<flag) {
						max1=flag;
						xiabiao=i;
						tap=true;
					}
					nu[i]--;
				}
			}
			if(tap) {
				nu[xiabiao]++;
				max = max+max1;
			}
			else break;
		}
		System.out.println(max);
	}
     
}