whyisyoung's Blog

If you can not persist, you will never succeed :)

EOJ 1488 Solution Report - Coin Collector

| Comments

原题:EOJ 1488

keyword: 贪心

1. 题目描述

某人有一个价值 K cents 的硬币去商店买东西,商店里有价值 1, 2, 3, … , K-1 cents 的货物。他买了其中一个货物,

该店的找零规则如下:

  1. 找回顾客 A cents

  2. 找回最大的面值不超过 A 的(设为 B cents),记还需找回顾客的钱为 A-B

  3. 如果 A - B = 0, 结束,否则返回第 2 步

求: 他可以收集多少种他还没有的硬币,以及在该情况下商店可以卖给他的最贵的货物是多少 cents?

Note:

$1 ≤ N ≤ 500, 000$

$2 ≤ K ≤ 1, 000, 000, 000$

$1 ≤ C_i < K $

$c1 < c2$ < … < c_N$

其中 $c_1 = 1$

2. 解题思路

本题数据较大,但是可以利用贪心,有以下四条规则:

  1. 硬币应该按照从小往大拿 ( 因为要尽可能多地收集硬币 )

  2. 已经拥有的直接忽略

  3. 比如 1 + 2 ≥ 3, 所以 2 是肯定不要找的,再比如 1 + 5 + 10 > 13, 所以 10 也是不在所求结果中的

  4. 每个硬币最多只要找回一次, 原因如下:

比如数据:

    2 28
    1 0
    13 0

如果找回两个 13 一个 1 的话,收集的硬币种类最多也还是只有两种,

倒不如找回一个 13 一个 1,这样找回的零钱最少,买到的东西最贵。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//
//  main.cpp
//  eoj 1488
//
//  Created by whyisyoung on 3/22/14.
//  Copyright (c) 2014 whyisyoung. All rights reserved.
//

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 500005;
int coin[maxn];
int possess[maxn];
int N, K;

int main()
{
    while(~ scanf("%d%d", &N, &K)) {
    	for(int i = 1; i <= N; ++i) {
    		scanf("%d%d", &coin[i], &possess[i]);
    		// TODO:
  			// getchar() 可以大幅提高速度....只是要加上一个处理函数
    	}

    	int ans = 0;
    	int tmp = 0;
    	coin[N+1] = K;

    	for(int i = 1; i <= N; ++i) {
    		if(possess[i] == 1)
    			continue;
    		else {
    			if(tmp + coin[i] >= coin[i+1])
    				continue;
    			else {
    				tmp += coin[i];
    				++ans;
    			}
    		}
    	}

    	if(ans == 0)
    		cout << 0 << endl << K - 1 << endl;
    	else
    		cout << ans << endl << K-tmp << endl;
    }
    return 0;
}

Comments