首页 > 代码库 > TopCoder SRM 639 Div.2 500 AliceGameEasy --乱搞
TopCoder SRM 639 Div.2 500 AliceGameEasy --乱搞
题意： 一个游戏有n轮，有A和B比赛，谁在第 i 轮得胜，就获得 i 分，给出x,y，问A得x分，B得y分有没有可能，如果有，输出A最少赢的盘数。
解法： 这题是我傻逼了，处理上各种不优越，要使n*(n+1)/2 >= 10^12， n为10^6是不够的，要开大一点，总是细节地方不注意。
做法很简单，先用map或者其他什么东西判断x+y是否为某个n*(n+1)/2， 如果不是，那肯定为-1，再就是x=0有可能要单独考虑，然后就是选一些数凑成x，由于要最少，那么从大的开始凑起，可以暴力地凑，也可以按n,n-1,...1排好，然后搞出前缀和，取个lower_bound,可知，结果就是lower_bound的值，因为左边能满足肯定优先选左边的，直到不满足再从后面选一个且肯定只是1个，所以是对的。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <map>#define ll long longusing namespace std;map<ll,int> mp;class AliceGameEasy{public: void init() { mp.clear(); ll now = 1; mp[1] = 1; for(int i=2;i<=3500000;i++) { now += i; mp[now] = i; } } ll sum[3500036]; long long findMinimumValue(long long x, long long y) { init(); if(x + y == 0) return 0; if(!mp[x+y]) return -1; if(x == 0LL) return 0; int n = mp[x+y]; sum[0] = 0; for(int i=1;i<=n;i++) sum[i] = sum[i-1] + (n-i+1LL); int ind = lower_bound(sum+1,sum+n+1,x)-sum; return ind; }};
TopCoder SRM 639 Div.2 500 AliceGameEasy --乱搞
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。