F.Permutation
题意
给一个n，构造一个1~n的序列使得 pi ≡ 0 ( mod |pi−pi−2| ) for i=3...n
分析
直接暴力让p[i]- p[i-2]=1，先安排奇数位置再安排偶数位置即可
时间复杂度O（n）
#include <cstdio> #include <cmath> #include<iostream> #include <algorithm> #define maxn 2000000+10 using namespace std; int a[505]; int b[505]; int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); int maxx = 0; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } int sum = 0; for(int i = 2; i <= n; i++) { sum+=a[i]-a[i-1]-1; } printf("%d ", max(sum-(a[2]-a[1]-1), sum-(a[n]-a[n-1]-1))); } return 0; }
H.A Simple Stone Game
题意
给n堆石头，每堆a[i]个， 每次可以从任意一堆拿走一颗石子，放到另一堆中，若存在x（x>1）使当前每堆石头b[i]都满足
b[i]%x=0则停止，问最小步数。（0%x=0）
分析
考虑若每堆石子是x的倍数，则石子总和sum是x的倍数，则x是sum的因子，所以对sum分解质因子，枚举质因子，然后贪心的把余数换点即可，对每一个质因子取min即可
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn =1e6+10; set<ll>s; vector<ll>g; ll a[maxn]; int n; void init(ll n) { for(ll i=2;i*i<=n;i++) { if(n&&n%i==0) { while(n%i==0) { n/=i; } s.insert(i); } } if(n>1) s.insert(n); } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d", &n); ll sum = 0; s.clear(); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum+=1ll*a[i]; } init(sum); ll minx = 1e10+10; for(auto it = s.begin(); it != s.end(); it++) { ll num = *it; g.clear(); ll sum1= 0; for(int i = 1; i <= n; i++) { if((a[i]%num)!=0) { g.push_back(a[i]%num); sum1+=a[i]%num; } } sort(g.begin(),g.end()); int st = 0, ed = g.size()-1; ll cnt = 0; for(int i=(int)g.size()-1;i>=0;i--) { cnt+=num-g[i]; sum1-=num; if(sum1<=0) break; } minx=min(minx,cnt); } printf("%lld ", minx); } return 0; }