文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

銷售主管的任務(wù)是出售一系列的物品，其中每個(gè)物品都有一個(gè)編號(hào)。

由于出售具有相同編號(hào)的商品會(huì)更容易，所以銷售主管決定刪除一些物品。

現(xiàn)在她知道她最多能刪除多少物品，她想知道最終袋子里最少可以包含多少種不同編號(hào)的物品。

例如，最開始她有n = 6 個(gè)物品，編號(hào)為：ids = [1,1,1,2,2,3]，她最多可以刪除 m = 2 個(gè)物品。

如果刪除兩個(gè)物品 1，則剩下的物品 ids = [1,2,2,3]，此時(shí)她擁有三種不同編號(hào)的物品。

如果刪除兩個(gè)物品 2，則剩下的物品 ids = [1,1,1,3]，此時(shí)她擁有兩種不同編號(hào)的物品。

如果刪除物品 2 和物品 3 各 1個(gè)，則剩下的物品 ids = [1,1,1,2]，此時(shí)她擁有兩種不同編號(hào)的物品。

我們發(fā)現(xiàn)，物品最少可以剩下兩種不同的編號(hào)，所以你的程序要返回 2

ids 的大小不超過 10^5 1 <= ids[i] <= 1000000 1 <= m <= 100000樣例 1 輸入： [1,1,1,2,2,3] 2 輸出： 2

https://tianchi.aliyun.com/oj/245809026182441523/267721733825565365

2. 解題

• 個(gè)數(shù)少的物品先拿走，減少的種類多

class Solution { public:/*** @param ids: ID number of items* @param m: The largest number of items that can be remove* @return: the result of the min item*/int minItem(vector<int> &ids, int m) {// write your code hereunordered_map<int,int> goods_count;for(auto i : ids)goods_count[i]++;vector<int> count;for(auto &gc : goods_count)count.push_back(gc.second);sort(count.begin(), count.end());int kinds = count.size(), i = 0;while(i < kinds && m > 0){int take = min(m, count[i]);m -= take;count[i] -= take;if(count[i] == 0)i++;}return kinds-i;} };

50ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的天池 在线编程 聪明的销售（计数+贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。