A - Sorted Adjacent Differences
题解：给出长度为n的数组，要求重新排列使
|a1−a2|≤|a2−a3|≤…≤|an−1−an|成立。。。。。方法：现将数组从大到小排列，若n为偶数，则从中间开始向两边数依次放到前面排列为新的数组，若为奇数，则最中间的数为第一个，再依次向两边放到前面
如 -2 4 5 5 6 8 --> 5 5 4 6 -2 8
1 3 5 7 9 >> 5 3 7 1 9
#include<bits/stdc++.h> #include<cstring> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; int s[n+5],i,j,b[n+5]; for(i=0;i<n;i++)cin>>s[i]; sort(s,s+n); int p=0; if(n%2==0) { i=n/2-1; int h=i; for(i=n/2-1;i>=0;i--) { b[p++]=s[i]; for(j=h+1;j<h+2;j++){ b[p++]=s[j]; } h++; } for(i=0;i<n;i++)cout<<b[i]<<" "; cout<<endl; } else { b[p++]=s[n/2]; int w=n/2+1; for(i=n/2-1;i>=0;i--) { b[p++]=s[i]; for(j=w;j<w+1;j++) { b[p++]=s[j]; } w++; } for(i=0;i<n;i++)cout<<b[i]<<" "; cout<<endl; } } }
题意：给出一组数，使该数组变为递增序列，在第x秒可以选择其中的一个或几个数增加2^(x-1),求使用的最少秒数
因为每秒都可以使任意数增加，所以直接找到递减的最大的值，计算出2的多少倍，求出x
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n,i,j; cin>>n; int s[n+5]; for(i=0;i<n;i++)cin>>s[i]; int m=0,p=s[0],k=0; for(i=1;i<n;i++) { if(m<p-s[i]) { k=1; m=p-s[i]; } //cout<<m<<endl; if(p<s[i])p=s[i]; } int ct=0; if(k==0)cout<<"0"<<endl; else { while(m) { ct++; m/=2; } cout<<ct<<endl; } } }
题意：给出一组数，从中任意选出几个数，求平均值，若达到标准数值则为有钱人，求最大数量的有钱人数
现将数组从大到小排序，每个数减去标准值，将差值加到下一个数上，差值大于等于0则满足要求
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { long long n,x; cin>>n>>x; long long s[n+5],i,j; for(i=0;i<n;i++)cin>>s[i]; sort(s,s+n,greater<int>()); long long ct=0,p,k=0; for(i=1;i<n;i++) { p=s[i-1]; if(p>=x) { ct++; k=p-x; s[i]+=k; //cout<<ct<<" "<<k<<" "<<s[i]<<endl; } } if(s[n-1]>=x)ct++; cout<<ct<<endl; } }
题意：n个怪物围成一个圈，每个怪物血量为ai爆炸伤害为bi，怪物被杀死后对下一个怪物造成爆炸伤害，每发子弹对怪物造成1点伤害，求杀死怪物的最少子弹数
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=300009; ll t,n,a[maxn],b[maxn],c[maxn],explore,sumn,minn=1e18; int main() { cin>>t; while(t--) { minn=1e18,sumn=0,explore=0; int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%lld%lld",&a[i],&b[i]); sumn+=a[i]; } for(int i=1;i<=n-1;i++) { c[i]=min(b[i],a[i+1]),explore+=c[i]; minn=min(minn,c[i]); } c[n]=min(b[n],a[1]); minn=min(minn,c[n]); explore+=c[n]; cout<<sumn-explore+minn<<endl; } }
题意：给出两个数组a和b，数组a由1 0 -1 组成，使数组a中任意数加上该数前面的数，多次操作后数组a等于数组b则输出YES 否则输出NO
先看a中与数组b不同的数的下标前是否存在1 或-1，并记录下来就行
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; long long s[n+5],b[n+5],w[n+5]={0},a[n+5]={0},i,j; int p=0,q=0; for(i=0;i<n;i++) { cin>>s[i]; if(p==1)w[i]=1;//只要在其本身之前出现一次-1，1，后面就都可以使用该处w[i]=1时，i>=2避免是本身下标 if(q==1)a[i]=-1; if(s[i]==1)p=1; else if(s[i]==-1)q=1; } for(j=0;j<n;j++)cin>>b[j]; int k=0; for(i=0;i<n;i++) { k=0; if(s[i]>b[i]) { if(a[i]==-1) k=1; } else if(s[i]<b[i]) { if(w[i]==1)k=1; } if(s[i]==b[i])k=1; //cout<<k<<endl; if(k==0){ cout<<"NO"<<endl; break; } } if(k==1)cout<<"YES"<<endl; } }
题意：如果一个数组的所有子数组，每个子数组数组元素和不为0，那么这是一个好数组，给你一个数组，计算它的子数组有多少是好数组
要解决题目所求首先就是找到和为0的子数组，这个在求一遍前缀和之后很容易看出，如果说前缀和数组中某两个位置的值相等（设这两个位置为left和right，即满足sum[left]==sum[right] ，那么区间[left+1,right]这一段的和必然为0。分析到这一步之后，我们尝试使用尺取法，定义双指针left,right 从左到右枚举答案区间的右端点right，并且移动left指针，以保证每一时刻双指针管辖的范围内不存在和为0的子数组序列，这个时候，以right为右端点对应的贡献就是right−left，我们把它累加到答案中即可。
具体实现时可以使用一个map 来实时更新标记区间中的情况。注意一个细节，要考虑某位置的前缀和为0 的情况，这个时候相当于是和sum[0]相等，所以一开始要初始化标记sum[0] 。
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 100; typedef long long ll; ll n, a, sum[maxn]; map<ll, bool> mp; ll solve(){ //尺取 ll ans = 0, left = 0, right = 1; //以right为答案区间的右端点，从左到右枚举 mp[0] = true; while(right <= n){ while(mp[sum[right]]){ mp[sum[left]] = false; ++left; } ans += right - left; mp[sum[right]] = true; ++right; } return ans; } int main(){ ll i, j; ios::sync_with_stdio(false); cin>>n; for(i=1;i<=n;++i){ cin>>a; sum[i] = sum[i-1] + a; } cout<<solve(); return 0; }
原文：https://www.cnblogs.com/mxw000120/p/12974605.html