A. Game
题意：
有n块相邻的土地，只有1可以走，0就不能走，你有一次超级跳的机会，每次多跳一格就会多消耗一金币，求最少的花费。
思路：
注意只能跳一次，然后必须要能够达到终点，那么从头和尾分别找第一个出现的0，然后算一下差距即可。
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t,d1; cin>>t; while(t--) { int flag1=0,flag2=0; cin>>n; vector<int >a; for(i=1;i<=n;i++) { cin>>j; a.push_back(j); } for(i=0;i<n;i++){ if(a[i]==0){ flag1=i+1; break; } } if(flag1==0){ cout<<0<<endl; continue; } for(i=n-1;i>=0;i--){ if(a[i]==0){ flag2=i+2; break; } } cout<<flag2+1-flag1<<endl; } return 0; }
B. Game of Ball Passing
题意：
知道每个球员的传球次数，求最少要几个球能完成每个人的传球要求
思路：
不难想到应该是答案应该是取决于需要传球次数最多的人，然后如果最多传球次数的两倍小于等于传球总数，那么只需要一个球就行了，例如1,2,3,3，总数8，但是最大的次数才3次，那么他们肯定可以两两传完，否则就输出他们的差即可。
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=1e5+100; long long a[maxn]; signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); long long n,i,j,t; cin>>t; while(t--){ cin>>n; long long l=0,r=0; for(i=0;i<n;i++){ cin>>a[i]; r+=a[i]; l=max(l,a[i]); } if(l==0){ cout<<0<<endl; } else if(l*2<=r){ cout<<1<<endl; } else { cout<<l-(r-l)<<endl; } } return 0; } /* 10 4 999999999 999999999 9999999999 1 */
C. Weird Sum
题意：
给你一个矩阵，每个位置都填上一个数，然后求相同数的任意两点之间的曼哈顿距离之和是多少？
思路:
首先要从曼哈顿距离去考虑这题，曼哈顿距离简单来说就是两个点之间的横坐标差+纵坐标差的和，接下来就去思考，如果都填一个数，怎么快速的算出来他们任意两个点之间的差距呢？
这里假设他们相同的数字有五个，他们横坐标分别是1,3,5,7
那么考虑他们每个点对答案的贡献就如下：
| 对于i点，能造成答案贡献的有a-b,a表示终点，b表示起点，3-1代表1到3需要2 | |||
| 1： | （3-1） | （5-1） | （7-1） |
| 3： | （5-3） | （7-3） | |
| 5： | （7-5） | ||
7： |
|||
再把加法和减法分开来看，就可以发现按顺序排列之后会有规律:
| 加法： | +7*3 | +5*2 | +3*1 |
| 减法： | -1*3 | -3*2 | -5*1 |
再把式子一提取一下，那么对于每个点a[i]，对答案的贡献就是i*a[i]-(n-i)*a[i]
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; #define int long long signed main() { int n,m,i,j,d1; map<int ,vector<int > >x,y; cin>>n>>m; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>d1; x[d1].push_back(i); y[d1].push_back(j); } } long long ans=0,c=0; for(auto &[a,b]:x) { int c=0; sort(b.begin(),b.end()); for(auto c1:b) { ans+=c1*c; c++; ans-=c1*(b.size()-c); } } for(auto &[a,b]:y) { int c=0; sort(b.begin(),b.end()); for(auto c1:b) { ans+=c1*c; c++; ans-=c1*(b.size()-c); } } cout<<ans<<endl; return 0; }
