---

思考難度低，但是代碼難度相對較高的題，故做個記錄。

首先，題目說了要花費最少的錢，所以我們每次拿最便宜的材料給武器1

思想：每次都拿最便宜的材料

然后考慮一下這個思想是否正確，找一下反例，每次拿一個材料給武器1，可以讓他增加一個。

那很明顯，如果我們除了武器1之外的，最多的那個材料，不管他的價格是多少，拿掉他，給武器1，相當于直接讓武器增加了2個材料（此消彼長）

所以有沒有一種可能，拿兩次最便宜的材料，不如拿一個材料種類最多的武器？

可以舉出一個反例：3 3/ 4，3+3塊錢貢獻了2個，4塊錢也貢獻了2個，顯然我們的核心思想需要改變。

改進思想：每次都拿最便宜的材料

1、如果此材料在 武器.材料種類 最多的武器上，直接執行

最便宜的1次操作實現了2次貢獻，很顯然已經沒有收益更高的操作了，這一步沒問題

2、如果此材料不在 武器.材料種類 最多的武器上；考慮對比 武器.材料種類 最多的武器

前者操作：令最便宜的花費為 cheapst，對武器1的貢獻 是1，每單位貢獻花費cheapst

后者操作：設花費為k（武器.材料種類 最多的武器可能有多個，所以這一步也要拿這些武器中最便宜的材料），對武器1的貢獻 是2，每單位貢獻花費 k/2

所以需要對比這兩者哪個更加劃算，由于k/2可能需要浮點數很麻煩，對比的時候直接把cheapst*2就可以。

顯然，已經找不出來更劃算的操作了，易得這一步也是沒問題的。

根據思想來實現全部功能，思想其實很容易定下來，但是這代碼就相當難寫了，AC代碼如下所示。

#include <bits/stdc++.h>
#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;const int N=1006;int n,m,ans;
int p[N],c[N];struct Material {int idx;int adapt;int cost;
}mat[N];
struct matCMP{bool operator()(Material a,Material b) {if (a.cost==b.cost) {return a.idx<b.idx;}return a.cost<b.cost;}
};
struct Weapon{int idx;set<Material,matCMP>mat;
}wea[N];//返回 武器.材料種類最多的 所有武器（除了武器1）
vector<Weapon>f() {int cnt=0;per(i,2,n) {cnt=max(cnt,(int)wea[i].mat.size());}vector<Weapon>res;per(i,2,n) {if (wea[i].mat.size()==cnt) {res.push_back(wea[i]);}}return res;
}
//返回最便宜的材料價格（除了武器1）
int g() {int res=INT_MAX;per(i,2,n) {if (wea[i].mat.size()) {res=min(res,(*wea[i].mat.begin()).cost);}}return res;
}
bool act1() {//最便宜的材料在 武器.材料種類最多的 武器上//直接執行vector<Weapon>v=f();int cheapst=g();per(i,0,v.size()-1) {if (v[i].mat.size()) {int val=(*v[i].mat.begin()).cost;if (val==cheapst) {wea[1].mat.insert(*v[i].mat.begin());wea[v[i].idx].mat.erase(wea[v[i].idx].mat.begin());ans+=val;return true;}}}return false;
}
void act2() {//cheap得到1貢獻  ~  約等于 2*chep得到2貢獻//武器.材料種類最多的 武器上，k得到2貢獻int cheap=g()*2;vector<Weapon>v=f();bool flag=false;//不拿最便宜的更劃算int idx=-1;per(i,0,v.size()-1) {if (v[i].mat.size()) {if ((*v[i].mat.begin()).cost<cheap) {if (flag==false) {flag=true;idx=i;}else {if ((*v[i].mat.begin()).cost<(*v[idx].mat.begin()).cost)idx=i;}}}}if (flag) {//拿v[idx]的最便宜材料wea[1].mat.insert(*v[idx].mat.begin());wea[v[idx].idx].mat.erase(wea[v[idx].idx].mat.begin());ans+=(*v[idx].mat.begin()).cost;}else {//拿最便宜的材料cheap>>=1;ans+=cheap;per(i,2,n) {if (wea[i].mat.size()) {if ((*wea[i].mat.begin()).cost==cheap) {wea[1].mat.insert(*wea[i].mat.begin());wea[i].mat.erase(wea[i].mat.begin());break;}}}}
}void solve() {cin>>n>>m;per(i,1,n)wea[i].idx=i;per(i,1,m) {cin>>p[i]>>c[i];mat[i].idx=i;mat[i].adapt=p[i];mat[i].cost=c[i];wea[p[i]].mat.insert(mat[i]);}if (n==1) {cout<<0<<endl;return;}while (wea[1].mat.size()<=f()[0].mat.size()) {if (!act1())act2();}cout<<ans<<endl;
}signed main() {ios::sync_with_stdio(false), cin.tie(nullptr);int t = 1;while (t--)solve();return 0;
}

不僅如此，還有兩個注意點

1、因為n>=1，所以n=1的時候，不需要任何操作，直接輸出0

2、自定義容器排序，set里面，如果只用 a.cost<b.cost，那么set保持升序的時候a.cost==b.cost會被直接去重，需要讓他們cost相等時，按照永遠不會相等的值來排序，或者直接用multiset

個人認為，思維難度大概，代碼難度至少

觀察發現，數據范圍相當小，更進一步從貢獻角度考慮，每次操作，我們去計算材料對武器1的 每單位貢獻花費，枚舉所有材料就可以了，此時他就是一個完美的