首页 > 代码库 > UVA 5986 - Wizarding Duel 超级脑洞题
UVA 5986 - Wizarding Duel 超级脑洞题
给出n个人，每个人两两比赛一场，一共有C(n,2)场比赛，现在给出一个榜，问其是否合法。不合法的话，就改成合法，输出最小需要改的变化。
分数一定是C(n,2)的了，
不和法的情况，比如0,0,2，是不行的，因为如果第一个人没赢过，那么第二个人绝对有赢过，起码赢了1啊，所以这个是不合法的。那么怎么做呢？
先从小到大排序，顺序是没关系的，我们不在意比分，只在意结果。然后对于前i个人，比分一定是C(i,2)这样才是合法的。不够的话，要补上，就比如0,0这样，我应该要ans += 1，因为前2个人的比分不够啊。那么我可能第三个人的比分补上来啊！！0,0,3，这样不行？是不行的，因为我们枚举的i，意义是满足前i个人互相比赛的结果，少了，自然要补。多了呢？无视，因为它可能是赢了后面的队伍。所以最后的时候，如果总比分比C（n,2）还要大的话，就要降下来，要加上差值。
很难想啊。。我是看题解的。。
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 50 +20;int a[maxn];bool cmp (int a,int b){ return a<b;}int C (int n,int m){ return n*(n-1)/2;}void work (){ int n; cin>>n; for (int i=1;i<=n;++i) cin>>a[i]; sort(a+1,a+1+n); int ans=0; int t=0; for (int i=1;i<=n;++i) { t += a[i]; if (t < C(i,2)) { ans += C(i,2) - t; t = C(i,2); } } if (t > C(n,2)) ans += t - C(n,2); cout<<ans<<endl;}int main(){#ifdef local freopen("data.txt","r",stdin);#endif int t; scanf("%d",&t); while (t--) work(); return 0;}
UVA 5986 - Wizarding Duel 超级脑洞题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。