Last active
December 30, 2015 07:59
-
-
Save todoa2c/7799667 to your computer and use it in GitHub Desktop.
https://paiza.jp/poh/ec-campaign の問題。
結果は下記の通りで、まだまだ速くない。二分探索とか使えば良くなるかも。
http://paiza.jp/poh/ec-campaign/result/20a50831ea10895508fc048be6e45667
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.BufferedReader; | |
| import java.io.IOException; | |
| import java.io.InputStreamReader; | |
| import java.util.ArrayList; | |
| import java.util.Comparator; | |
| import java.util.List; | |
| import java.util.Map; | |
| import java.util.TreeMap; | |
| /** | |
| * https://paiza.jp/poh/ec-campaign | |
| */ | |
| public class Main { | |
| public static void main(String[] args) throws IOException { | |
| List<Integer> productPrices; | |
| List<Integer> campaignPrices; | |
| // 重複除去用 | |
| Map<Integer, Integer> productPriceCounter = new TreeMap<>(new Comparator<Integer>() { | |
| @Override | |
| public int compare(Integer o1, Integer o2) { | |
| return o2 - o1; | |
| } | |
| }); | |
| // 条件の読み込み | |
| try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) { | |
| String line; | |
| line = reader.readLine(); | |
| String[] patterns = line.split("\\s"); | |
| int productNum = Integer.parseInt(patterns[0]); | |
| int campaignNum = Integer.parseInt(patterns[1]); | |
| campaignPrices = new ArrayList<>(campaignNum); | |
| for (int i = 0; i < productNum; i++) { | |
| Integer price = Integer.valueOf(reader.readLine()); | |
| Integer count = productPriceCounter.get(price); | |
| productPriceCounter.put(price, count == null ? 0 : count + 1); | |
| } | |
| for (int i = 0; i < campaignNum; i++) { | |
| campaignPrices.add(Integer.valueOf(reader.readLine())); | |
| } | |
| } | |
| productPrices = new ArrayList<>(); | |
| for (Map.Entry<Integer, Integer> entry : productPriceCounter.entrySet()) { | |
| productPrices.add(entry.getKey()); | |
| if (entry.getValue() > 1) { | |
| productPrices.add(entry.getKey()); | |
| } | |
| } | |
| for (Integer campaignPrice : campaignPrices) { | |
| List<Integer> prices = new ArrayList<>(productPrices.size()); | |
| // キャンペーン価格より高い商品は事前に除去 | |
| for (Integer productPrice : productPrices) { | |
| if (productPrice < campaignPrice) { | |
| prices.add(productPrice); | |
| } | |
| } | |
| // 除去した結果の商品が2コ以上あれば本格的な探索 | |
| int result; | |
| if (prices.isEmpty()) { | |
| result = 0; | |
| } else if (prices.size() == 1) { | |
| result = prices.get(0); | |
| } else { | |
| result = calcMaxPrice(prices, campaignPrice); | |
| } | |
| System.out.println(result); | |
| } | |
| } | |
| private static Integer calcMaxPrice(List<Integer> prices, Integer campaignPrice) { | |
| Integer maxPrice = 0; | |
| int maxI = prices.size() - 1; | |
| Integer minPrice = prices.get(prices.size() - 1); | |
| // TODO 二分探索の検討 | |
| for (int i = 0; i < maxI; i++) { | |
| Integer item1 = prices.get(i); | |
| // item1と一番安い価格の組み合わせがキャンペーン価格より高ければitem1を次のものにする | |
| if (item1 + minPrice > campaignPrice) { | |
| continue; | |
| } | |
| for (int j = i + 1; j < prices.size(); j++) { | |
| Integer item2 = prices.get(j); | |
| int price = item1 + item2; | |
| // 高すぎ → 次のitem2へ | |
| if (price > campaignPrice) { | |
| continue; | |
| } else if (price == campaignPrice) { | |
| // ピッタリ → 計算終了 | |
| return price; | |
| } else if (price > maxPrice) { | |
| // 最高価格更新 → 次のitem1で調査 | |
| maxPrice = price; | |
| break; | |
| } else { | |
| // 最高価格でなければitem2をそれ以上見る必要がない → 次のitem1へ | |
| break; | |
| } | |
| } | |
| } | |
| // 最後まで計算したら、その時点の最高額を返す | |
| return maxPrice; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment