• 贪心算法 Heidi and Library (easy)

    A. Heidi and Library (easy)

    time limit per test

    2 seconds

    memory limit per test

    256 megabytes

    input

    standard input

    output

    standard output

    Your search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are n different books, numbered 1 through n.

    We will look at the library's operation during n consecutive days. Heidi knows in advance that on the i-th day (1 ≤ i ≤ n) precisely one person will come to the library, request to borrow the book ai, read it in a few hours, and return the book later on the same day.

    Heidi desperately wants to please all her guests, so she will make sure to always have the book ai available in the library on the i-th day. During the night before the i-th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books.

    There is a problem, though. The capacity of the library is k – this means that at any time, there can be at most k books at the library. If buying a new book would cause Heidi to have more than k books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again.

    You are given k and the sequence of requests for books a1, a2, ..., an. What is the minimum cost (in CHF) of buying new books to satisfy all the requests?

    Input

    The first line of input will contain two integers n and k (1 ≤ n, k ≤ 80). The second line will contain n integers a1, a2, ..., an(1 ≤ ai ≤ n) – the sequence of book requests.

    Output

    On a single line print the minimum cost of buying books at the store so as to satisfy all requests.

    Examples

    input

    4 80
1 2 2 1

    output

    2

    input

    4 1
1 2 2 1

    output

    3

    input

    4 2
1 2 3 1

    output

    3

    Note

    In the first test case, Heidi is able to keep all books forever. Therefore, she only needs to buy the book 1 before the first day and the book2 before the second day.

    In the second test case, she can only keep one book at a time. Therefore she will need to buy new books on the first, second and fourth day.

    In the third test case, before buying book 3 on the third day, she must decide which of the books 1 and 2 she should get rid of. Of course, she should keep the book 1, which will be requested on the fourth day.

    #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 88
#define MOD 1000000
#define INF 1000000009
#define eps 0.00000001
/*
贪心策略错误！每次需要去掉元素的时候，不是去掉以后出现次数最多的元素，
去掉下一次出现位置最晚的元素！这个元素占用图书馆空间的时间最长！
*/
int cnt[MAXN], a[MAXN], pos[MAXN];
int n, k;
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    set s;
    int tmp = 0;
    for (int i = 0; i < n; i++)
    {
        if (!s.count(a[i]))
        {
            if (s.size() == k)
            {
                int Max = -INF, p = -1;
                for (auto it = s.begin(); it != s.end(); it++)
                {
                    int j;
                    for (j = i; j < n; j++)
                    {
                        if (a[j] == *it)
                        {
                            break;
                        }
                    }
                    if (j > Max)
                    {
                        Max = j;
                        p = *it;
                    }
                }
                s.erase(p);
                //cout << "::::::::::::::" << p << endl;
            }
            s.insert(a[i]);
            tmp++;
        }
    }
    printf("%d\n", tmp);
}
  • 相关阅读:
    鸡得关节炎有哪些症状 鸡喂什么药预防球菌病
    Linux 安装Nginx详细图解教程
    扩散模型：DDPM代码的学习（基于minist数据集）
    基于知识蒸馏的两阶段去雨去雪去雾模型学习记录（一）
    如何在 Java 中实现二叉搜索树
    B树、B+树详解
    知物由学 | AI与黑产的攻守之道，详解攻击类文字图像的检测
    [Spring Boot 6]企业级开发
    计算机竞赛 大数据疫情分析及可视化系统
    电子竞赛1——基于DDS的AM信号发生器
  • 原文地址：https://blog.csdn.net/apple_51426592/article/details/128009760