本文主要是介绍比武定工资，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
由于粉丝众多，何老板出门经常遇到粉丝们的围堵，这让何老板很是烦恼。于是何老板雇佣了n个保镖。怎样给保镖们定工资，这成了个大问题，保镖们个个都号称武林高手，于是何老板决定按照功夫的高低来定工资。何老板问：你们中谁的功夫最厉害？
“我！我会降龙十八掌！”
“我！我练过《葵花宝典》！”
“我！我会天马流星拳！”
“我！我会神龟冲击波！”
“我！我有钢铁侠套装！”
“我！我爸是李刚！”
…
保镖们吵得何老板头都要炸了，于是何老板决定，通过比武来决定工资的高低。何老板规定保镖的工资都是整数，最低工资是100元。若保镖x打赢了保镖y，那么x的工资应该比y的要高。对于这种方式，保镖们纷纷表示支持。
于是比武开始了，总共进行了m场比武，何老板想根据比武结果，找出一种工资方案，使得总的工资数最少。
输入格式
第一行两个空格间隔的整数n,m，表示保镖的总数和比武的场数；
接下来m行，每行两个空格间隔的整数x,y，表示这场比武x号保镖打赢了y号保镖。
输出格式
若不能找到合理的工资方案，则输出“no solution”；否则输出一个整数表示最少的工资数。
样例输入 1
7 4
1 2
3 4
5 1
3 4
样例输出 1
704
样例输入 2
7 10
5 3
7 4
4 3
7 6
1 2
4 3
5 2
5 6
3 6
2 3
样例输出 2
714
提示
5打赢1，1打赢2。2的工资是100,1的工资是101,5的工资是102
3打赢4。4的工资是100,3的工资是101
6和7没有参与比赛，拿最低工资100
总计704
80％的数据满足n<=1000，m<=2000；
100％的数据满足n<=6000，m<=20000
不说了，上代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a[10005][305],b[10005],c[10005],m,n,x,y,ans;
bool check(){ll t,tot=0,k=0;while(tot<n){t=0;for(int i=1;i<=n;i++)if(b[i]==0){tot++;t++;ans+=100;c[t]=i;b[i]=INT_MAX;}if(t==0)return false;ans+=k*t;k++;for(int i=1;i<=t;i++)for(int j=1;j<=a[c[i]][0];j++)b[a[c[i]][j]]--;}return true;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);a[y][0]++;a[y][a[y][0]]=x;b[x]++;}if(check())cout<<ans;else cout<<"no solution";return 0;
}
这篇关于比武定工资的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
