[JAVA] ABC --127 --A & B & C

AtCoder ABC 127 A&B&C&D AtCoder - 127

I'll be back to solve E & F in the near future.

2019/05/27 B code fix

A - Ferris Wheel

	private void solveA() {
		int a = nextInt();
		int b = nextInt();

		if (a <= 5) {
			out.println(0);
		} else if (a <= 12) {
			out.println(b / 2);
		} else {
			out.println(b);
		}
	}

B - Algae

• x_{2001}=r \times x_{2000}−D
• x_{2002}=r \times x_{2001}−D -・ -・
• x_{i+1}=r \times x_i−D

	private void solveB() {
		int r = nextInt();
		int d = nextInt();
		int x2000 = nextInt();

		int pre = x2000;
		for (int i = 1; i <= 10; i++) {
			pre = r * pre - d;
			out.println(pre);
		}

	}

C - Prison

--Input example 1

4 2 1 3 2 4

--The first gate opens with the 1,2,3 keys --The second gate opens with the 2, 3 and 4 keys --A few keys can open both gates --Find the key used in all gates

I replaced it with a number.

A key with total = number of gates can open all doors. The process of adding from a certain range to a certain range is faster with the potato method.

So I will post the usual reference site list

--Reference site (potato method and cumulative sum) -Imotz method -Summary of imos method / cumulative sum problem in competitive programming -Be able to write the cumulative sum without thinking!

		int n = nextInt();
		int m = nextInt();

		//For memo which number key is required at each gate
		int[] wk = new int[n];

		for (int i = 0; i < m; i++) {
			int l = nextInt() - 1;
			int r = nextInt() - 1;
			wk[l] += 1;
			if (r + 1 < n) {
				wk[r + 1] -= 1;
			}
		}

		//
		for (int i = 1; i < n; i++) {
			wk[i] += wk[i - 1];
		}
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (wk[i] == m) {
				cnt++;
			}
		}

		out.println(cnt);

D - Integer Cards

--Since the order of rewriting the cards is not specified ――It seems good to rewrite the small ones of the imported cards with the large ones.

1. Arrange A (cards taken in) (in ascending order here)
2. Arrange B (number of sheets) and C (integer) in C order (descending order here)
3. Compare with [B, C] in ascending order of A
4. Compare up to B sheets to see if C is larger than A, and rewrite A if C is larger
5. Repeat 3-4

――For the part 3, the following processing is performed in the code, but this is because "B and C are arranged in descending order, so the part once rewritten with C will not be rewritten after that (when rewritten C larger than C does not appear) " ――If you don't do this, you will run out of time due to extra processing.

 //There is no point in rewriting (comparing) the same place, so start is shifted.
        int start = 0;

--Whole code

	private void solveD() {
		int n = nextInt();
		int m = nextInt();
		long[] a = LongStream.range(0, n).map(i -> nextLong()).toArray();

		//Sort in ascending order
		Arrays.sort(a);

		int[][] bc = IntStream.range(0, m).collect(() -> new int[m][2],
				(t, i) -> {
					t[i][0] = nextInt();
					t[i][1] = nextInt();
				},
				(t, u) -> {
					Stream.concat(Arrays.stream(t), Arrays.stream(u));
				});

		//Sort in descending order of C
		Arrays.sort(bc, (x, y) -> -Integer.compare(x[1], y[1]));
		//There is no point in rewriting (comparing) the same place, so start is shifted.
		int start = 0;
		for (int j = 0; j < m; j++) {
			int max = Integer.min((start + bc[j][0]), n);
			for (int k = start; k < max; k++) {
				if (bc[j][1] > a[k]) {
					//a[i]Is smaller is rewritten
					a[k] = bc[j][1];
					//Preparing to shift the next start
					start = k + 1;
				} else {
					//It's already sorted, so a[i]No need to compare any more if is larger
					break;
				}
			}

		}
		//total
		long res = Arrays.stream(a).sum();

		out.println(res);
	}