A. Game
有 个横向排列的位置，序号为 ，每个位置可能有水，也可能是空的。
向相邻格子移动是不需要花费的。
在每组数据中，你只能跳一次。你可以跳任意格远。代价为 （ 为终点 为起点）
你不能跳到含水格子里。保证起点 和终点 没有水。
只能跳一次，那么说明我们只可能通过一次大跳来跳过所有含水格子。大跳的代价与距离成正比，所以大跳的距离越小越好。
那么，大跳就从最左边的水格子前起跳，跳到最右边的水格子后即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int k,ans=n+1,ans2=0;
for(int i=1;i<=n;i++)
{
cin>>k;
if(k==0) {ans=ans==n+1? i-1:ans;ans2=i+1;}
}
ans2=n-ans2;
if(ans==n+1) cout<<0<<endl;
else cout<<(n-ans-ans2)<<endl;
}
return 0;
}
|
B. Game of Ball Passing
传球游戏。在游戏的过程中，有 个人。他们将要互相传球。每个人传出球的次数是给定的（传入不算次数）。
那么，最少需要多少个球可以满足这些传球的次数呢？
比如说，第一组样例就可以只用一个球传出这种方案。
而第二组样例则不行。
重点在于如何利用 “每个人传出球的次数是给定的（传入不算次数）。”
找出踢球数最大的人，这个人的踢球数可以消耗其他人的踢球数。
若其他人的踢球数总和大于踢球数的人，这些人可以自己内部对踢（无论是一对一还是多对多，反正剩下的踢球数等于最大踢球数）。
但如果最大踢球数的人踢球的数量太大了，他跟其他人消耗后，还剩下了一些球数，只能他自己踢了（为什么？最多的情况下，即剩下人不内部踢球，只与最大踢球数的人踢，也只能消耗这些，还差一些）。
所以，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int t;
cin>>t;
while(t--)
{
int n,k,maxn=0,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>k;
maxn=max(maxn,k);
sum+=k;
}
if(maxn==0) cout<<0<<endl;
else
{
int ans=max(1ll,maxn-(sum-maxn));
cout<<ans<<endl;
}
}
return 0;
}
|