题意：对一组数重新排序，使得相邻两数的差的绝对值不减小
思路：我一开始不会做，后来看别人的，找到中位数。所以讲述从大到小排列，后从中位数开始向两头找，因为相差越远差值越大
#include<iostream> #include<algorithm> using namespace std; bool cmp(int a,int b){ return a>b; } int main(){ int t; cin>>t; while(t--){ int n,a[100007]; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1,cmp); if(n%2==0){for(int i=n/2,j=n/2+1;i>=1;i--,j++) cout<<a[j]<<" "<<a[i]<<" "; cout<<endl;} else{ int j,i; //cout<<n/2<<endl; for(i=n/2,j=n/2+1;i>=1;i--,j++) cout<<a[j]<<" "<<a[i]<<" "; cout<<a[j]<<endl; } } }
题意：找一个数最小的X,使数组中任意数加上2^(X-1)，成为不减数组
思路：我太笨了，最开始还是不会，后来有人告诉我，找到最大的和最小的，其差值，肯定可以弥补其他的，而只要，其他的不超过最后就可以，因为可以任意选数
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; #define ll long long #define N 1000000 ll a[N]; int main() { int t; cin>>t; while(t--){ int n,s=0; ll max1=0,ans=0; cin>>n; //memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ cin>>a[i]; } s=a[1]; for(int i=1;i<=n;i++){ if(max1<s-a[i]){ max1=s-a[i]; } if(s<a[i])s=a[i];//更新因为 2 8 10 9若不更，对于8来说，后面都对 } while(max1){ max1/=2; ans++; } cout<<ans<<endl; } }
题意：给你一个x（X是富人的标准），收一些人的钱，然后再分给这些人，问最多可以创造多少名富人
思路：我想的是从小到大排列后，用前缀和，从最后一个元素，两个，三个，不断暴力，直到不成为富豪
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; #define ll long long #define N 1000000 ll a[N],b[N]; int main() { int t; cin>>t; while(t--){ int n,x,sum1=0; cin>>n>>x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1;i<=n;i++){ cin>>b[i]; } sort(b+1,b+1+n); for(int i=1;i<=n;i++) a[i]+=a[i-1]+b[i]; for(int i=n-1;i>=0;i--){ double sum=(a[n]-a[i])/(n-i); if(sum>=x)sum1=n-i; else break; } cout<<sum1<<endl; } }
题意：题目问你最少需要的子弹数，子弹数是啥呢，，就是一颗子弹伤害为一滴血，有围成一圈的怪物，怪物血量为a,其爆炸伤害为b滴血，只要你将它弄死，他就会有b点伤害，要让所有怪物都死
思路：我不会做，，但是看了别人的会了，推导如下：
Input:
1
3
7 15
2 14
5 3
Output:
6
a1=7 b1=15
a2=2 b2=14
a3=5 b3=3
因(a2-b1)=(2-15)<0，故取值为a2-b1=0
因(a3-b2)=(5-14)<0，故取值为a3-b2=0
从位置1出发:消耗的子弹=a1+(a2-b1)+(a3-b2)=7+0+0=7
因(a3-b2)=(5-14)<0，故取值为a3-b2=0
因(a1-b3)=(7-3)>=0，故取值为a1-b3=4
从位置2出发:消耗的子弹=a2+(a3-b2)+(a1-b3)=2+0+4=6
因(a1-b3)=(7-3)>=0，故取值为a1-b3=4
因(a2-b1)=(2-15)<0，故取值为a2-b1=0
从位置3出发:消耗的子弹=a3+(a1-b3)+(a2-b1)=5+4+0=9
可以看到规律了:
a1+(a2-b1)+(a3-b2)
a2+(a3-b2)+(a1-b3)
a3+(a1-b3)+(a2-b1)
这3组数据中取最小值
#include <cstdio> #include<algorithm> using namespace std; const int N=3e5+7; #define ll long long ll a[N],b[N],c[N]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]); ll sum=0; for(int i=1;i<=n;i++) { if(i==1) c[i]=max(0ll,a[i]-b[n]);//0ll因为类型是long long else c[i]=max(0ll,a[i]-b[i-1]); sum+=c[i]; } ll ans=1e18; for(int i=1;i<=n;i++) ans=min(ans,sum-c[i]+a[i]); //sum是a1到a3减b1到b3,发现总是少一个才是得数 printf("%lld\n",ans); } } //cout,cin过不去，printf,scanf可以
题意：a数组只有0，1，-1三种类型的数，b数组各种数都有，问你通过操作能不能让a数组与b数组相等,操作方式如下：选取数对，如（1，3）就是将索引为1位置的数加到索引为3的位置的数上
思路：用map记录1，-1，0各种数的数量，从后往前遍历，只要前面有就能使其相等
#include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; #define ll long long #define N 1000005 ll a[N],b[N]; int main() { int t; cin>>t; while(t--){ map<int,int> w; int n,m=1;; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; w[a[i]]++; } for(int i=0;i<n;i++) cin>>b[i]; for(int i=n-1;i>=0;i--){ w[a[i]]--;//从后往前，用不到就去掉 if(b[i]>a[i]){ if(w[1]>0){} else m=0; } if(b[i]<a[i]){ if(w[-1]>0){} else m=0; } if(a[i]==b[i])continue; } if(m==1)cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
题意：简洁点就是，一个数组a，问其连续的（一定是连续的）子序列里，不能有加和为零的地方
思路：一言难尽，
我本来的思路：
#include<cstdio>
#include<cstring>
#define ll long long
#define N 1000000
using namespace std;
ll a[N],b[N];
int main()
{
int n;
scanf("%d",&n);
// map<int,int> q;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
ll sum=0;
for(int i=1;i<=n;i++){
memset(b,0,sizeof(b));
// int x=0;
for(int j=i;j<=n;j++){
b[j]+=b[j-1]+a[j];
if(b[j]!=0){
sum+=1;
}
else break;
}
}
printf("%lld\n",sum);
}
超时了，但思路是对的，就是求出其和为零的地方，从下一字母，其前缀不为零的地方开始
被人正确的
#include<iostream> #include<map> #include<cstdio> using namespace std; const int maxn = 2e5 + 10; long long dp[maxn]; int main() { map<long long, int> rec;//维护每个前缀和最近一次出现的位置 int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> dp[i], dp[i] += dp[i - 1]; rec[dp[i]] = -1; } long long ans = 0; int max_l = -1; rec[0] = 0; for (int i = 1; i <= n; i++) { if (rec[dp[i]] != -1) max_l = max(max_l, rec[dp[i]]); rec[dp[i]] = i; ans += i - (max_l + 1);/*max_l表示前缀和相等的下标，而max_l+1才是实际的区间，这样计算因为连续变成1+2+3这样，因为1，1 2，1 2 3，2，2 3，3，正好是*/ } cout << ans; return 0; }
//补充一下，这个意思是如1 2 -3 4 5 6显然1，2，-3为0，所以让max_1=3（第三个位置）开始，而之前是从最开始的位置开始，，，好像错了，但大概是这样
原文：https://www.cnblogs.com/1324a/p/12994618.html