「FZU2281」Trades【第一次寫java】

Trades

This is a very easy problem.

ACMeow loves G T X 1920. GTX1920. GTX1920. Now he has m m m R M B RMB RMB, but no G T X 1920 s GTX1920s GTX1920s. In the next n n n days, the unit price of G T X 1920 GTX1920 GTX1920 in the i − t h i-th i−th day is C i C_i Ci​ R M B . RMB. RMB. In other words, in the i − t h i-th i−th day, he can buy one G T X 1920 GTX1920 GTX1920 with C i C_i Ci​ R M B RMB RMB, or sell one G T X 1920 GTX1920 GTX1920 to gain C i C_i Ci​ R M B . RMB. RMB. He can buy or sell as many times as he wants in one day, but make sure that he has enough money for buying or enough G T X 1920 GTX1920 GTX1920 for selling.

Now he wants to know, how many R M B RMB RMB can he get after the n days. Could you please help him?

It’s really easy, yeah?

Input

First line contains an integer T ( 1 ≤ T ≤ 20 ) T(1 \leq T \leq 20) T(1≤T≤20), represents there are T T T test cases.

For each test case: first line contains two integers n ( 1 ≤ n ≤ 2000 ) n(1 \leq n \leq 2000) n(1≤n≤2000) and m ( 0 ≤ m ≤ 1000000000 ) . m(0 \leq m \leq 1000000000). m(0≤m≤1000000000). Following n n n integers in one line, the i − t h i-th i−th integer represents C i ( 1 ≤ C i ≤ 1000000000 ) . C_i(1 \leq C_i \leq1000000000). Ci​(1≤Ci​≤1000000000).

Output

For each test case, output “Case #X: Y” in a line (without quotes), where X X X is the case number starting from 1 1 1, and Y Y Y is the maximum number of R M B RMB RMB he can get mod 1000000007. 1000000007. 1000000007.

Sample Input

2
3 1
1 2 3
4 1
1 2 1 2
           

Sample Output

Case #1: 3
Case #2: 4
           

題意

• 就是有 n n n天，你開始有 m m m元錢，每天的顯示卡都有一個價格，你可以選擇把手中的一些顯示卡賣掉或者買進一些顯示卡（隻要錢夠），問最後你手上最多有多少錢

題解

• 昨天才開始學的一節課的 j a v a java java,今天就遇到了還是很開心 Q W Q QWQ QWQ
• 貪心：在一段連續的單調區間内，低谷買進顯示卡，高峰賣掉顯示卡，隻不過可能會爆 l o n g   l o n g long\ long long long，比如 1   1 0 9   1   1 0 9   1.... 1\ 10^9\ 1\ 10^9\ 1.... 1 109 1 109 1....這種情況，是以直接可以用 j a v a java java來寫

代碼

import java.util.*;
import java.math.*;

public class Main {
	public static void main(String args[]){
		int[] a=new int[2005];
		Scanner in=new Scanner(System.in);
		int t=in.nextInt();
		for(int cas=1;cas<=t;cas++) {
			int n=in.nextInt(),m=in.nextInt();
			for(int i=1;i<=n;i++) a[i]=in.nextInt();
			
			int l=1,r=1;
			boolean inc=true;
			while(r<n) {
				if(inc) {
					int pos=r;
					while(r<n&&a[r+1]>=a[r]) r++;
					if(a[pos]!=a[r]) a[++l]=a[r];
					inc=false;
				}else{
					int pos=r;
					while(r<n&&a[r+1]<=a[r]) r++;
					if(a[pos]!=a[r]) a[++l]=a[r];
					inc=true;
				}
			}
			n=l;
			BigInteger money=BigInteger.valueOf(m),have=BigInteger.valueOf(0);
			System.out.print("Case #"+cas+": ");
			if(n==1) {
				System.out.println(m);
				continue;
			}
			if(a[2]>a[1]) {
				have=money.divide(BigInteger.valueOf(a[1]));
				money=money.mod(BigInteger.valueOf(a[1]));
			}
			for(int i=2;i<=n;i++) {
				BigInteger c=BigInteger.valueOf(a[i]);
				if(a[i]>a[i-1]) {
					
					money=money.add(c.multiply(have));
					have=BigInteger.valueOf(0);
				}else {
					have=have.add(money.divide(c));
					money=money.mod(c);
				}
			}
			BigInteger c=BigInteger.valueOf(a[n]);
			money=money.add(c.multiply(have));
			System.out.println(money.mod(BigInteger.valueOf(1000000007)));
		}
	}
}