---

思考难度低，但是代码难度相对较高的题，故做个记录。

首先，题目说了要花费最少的钱，所以我们每次拿最便宜的材料给武器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的 每单位贡献花费，枚举所有材料就可以了，此时他就是一个完美的