3 条题解
-
1
贪心即可,考虑到通关的限制就是关卡中数值最大的敌人,我们先对所有敌人进行排序,根据题意模拟找出最大的数值即可。模拟过程中需要注意角色的数值仅需大于等于敌人,因此需要特判一下数值相等的情况。另外不开longlong见祖宗
void solve(){ ll n;cin>>n; vector<ll> a(n+1); for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a.begin()+1,a.end()); ll tmp=0,ans=0; for(int i=1;i<=n;i++){ if(tmp<a[i]){ if(a[i]%10 == 0){ tmp=(a[i]/10); } else tmp=(a[i]/10)+1; } ans=max(tmp-i+1ll,ans); } cout<<ans<<endl; }然而本题考查本意为二分答案,也可以轻松解决,此处给出参考代码
bool ok(ll L){ ll atk = 10 + (L - 1) * 10; // 初始战力 for(auto x : a){ if(atk < x) return false; atk += 10; // 打赢升级 +10 } return true; } int n; vector<ll> a; void solve(){ cin >> n; a.resize(n); for(int i = 0; i < n; i++) cin >> a[i]; sort(all(a)); ll l = 1, r = 1e17; // 上界很宽也没问题 while(l < r){ ll mid = (l + r) >> 1; if(ok(mid)) r = mid; else l = mid + 1; } cout << l; } -
0
题目是求通关等级的最小等级 二分答案加贪心即可 排序贪心最小值 二分答案求得符合条件等级中的最小值
def main(): import sys n = int(input()) data = list(map(int, sys.stdin.readline().strip().split())) data.sort() #检查是否可以过关 def k(x): total = 0 for i in data: if x >= i: x += 10 total += 1 if total == n: return True else: return False left = 1 right = max(data) ans = 0 while left <= right: mid = (left + right) // 2 if k(mid): #可以过关缩短右边界 均值向左侧接近 使mid更小 right = mid - 1 #存储最优解 防止最后mid不是答案的情况 ans = mid #无法过关left向右侧逼近 增大mid值 else: left = mid + 1 #向上取整 print((ans + 9) // 10) if __name__ == "__main__": main() #无注释版本: ```python def main(): import sys n = int(input()) data = list(map(int, sys.stdin.readline().strip().split())) data.sort() def k(x): total = 0 for i in data: if x >= i: x += 10 total += 1 if total == n: return True else: return False left = 1 right = max(data) ans = 0 while left <= right: mid = (left + right) // 2 if k(mid): right = mid - 1 ans = mid else: left = mid + 1 print((ans + 9) // 10) if __name__ == "__main__": main()
- 1
信息
- ID
- 1128
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 164
- 已通过
- 26
- 上传者