思维，一个数0，两个数m,三个数以上，先放0 m 0,结果是2*m
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j); i<(k); ++i)
#define pb push_back
#define PII pair<int,int>
#define PLL pair<long long, long long>
#define ini(a,j) memset(a,j,sizeof a)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define fi first
#define se second
#define LL long long
#define beg begin()
#define ed end()
#define all(x) x.begin(),x.end()
const int N=1e5+10;
int main(int argc, char const *argv[])
{
// #define DEBUG
#ifdef DEBUG
freopen("1.dat","r",stdin);
freopen("ans.dat","w",stdout);
#endif
int _;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>_;
while(_--){
int n,m;
cin>>n>>m;
if(n==1)
cout<<0<<endl;
else if(n==2)
cout<<m<<endl;
else
cout<<2*m<<endl;
}
return 0;
}
排序，然后贪心k次，如果当前A中最小的比b中最大的大，就交换
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j); i<(k); ++i)
#define pb push_back
#define PII pair<int,int>
#define PLL pair<long long, long long>
#define ini(a,j) memset(a,j,sizeof a)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define fi first
#define se second
#define LL long long
#define beg begin()
#define ed end()
#define all(x) x.begin(),x.end()
const int N=50;
int a[N];
int b[N];
int main(int argc, char const *argv[])
{
// #define DEBUG
#ifdef DEBUG
freopen("1.dat","r",stdin);
freopen("ans.dat","w",stdout);
#endif
int _;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>_;
while(_--){
int n,k;
cin>>n>>k;
rep(i,0,n)
cin>>a[i];
rep(i,0,n)
cin>>b[i];
sort(a,a+n);
sort(b,b+n);
for(int i=0; i<k; i++){
if(a[i]<b[n-i-1])
a[i]=b[n-i-1];
}
int ans=0;
rep(i,0,n)
ans+=a[i];
cout<<ans<<endl;
}
return 0;
}
递推，首先可以发现，挪到最中间那个格子，次数最小。然后是个递推
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j); i<(k); ++i)
#define pb push_back
#define PII pair<int,int>
#define PLL pair<long long, long long>
#define ini(a,j) memset(a,j,sizeof a)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define fi first
#define se second
#define LL long long
#define beg begin()
#define ed end()
#define all(x) x.begin(),x.end()
const int N=250010;
LL dp[N];
int main(int argc, char const *argv[])
{
// #define DEBUG
#ifdef DEBUG
freopen("1.dat","r",stdin);
freopen("ans.dat","w",stdout);
#endif
int _;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>_;
dp[0]=0;
for(LL i=1; i<N; i++)
dp[i]=dp[i-1]+(i-1)*(i-1);
while(_--){
int n;
cin>>n;
cout<<8*dp[(n+1)/2]<<endl;
}
return 0;
}
优先队列真的香，直接模拟
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j); i<(k); ++i)
#define pb push_back
#define PII pair<int,int>
#define PLL pair<long long, long long>
#define ini(a,j) memset(a,j,sizeof a)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define fi first
#define se second
#define LL long long
#define beg begin()
#define ed end()
#define all(x) x.begin(),x.end()
const int N=2e5+10;
int ans[N];
struct Cmp
{
bool operator ()(PII& a, PII& b){
if(a.se-a.fi==b.se-b.fi)//小的前面
return a.fi>b.fi;
else
return (a.se-a.fi)<(b.se-b.fi);
}
};
priority_queue<PII, vector<PII>,Cmp> pq;
int main(int argc, char const *argv[])
{
// #define DEBUG
#ifdef DEBUG
freopen("1.dat","r",stdin);
freopen("ans.dat","w",stdout);
#endif
int _;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>_;
int mid=0;
while(_--){
int n;
cin>>n;
pq.push(make_pair(1,n));
rep(i,1,n+1){
PII temp=pq.top();
pq.pop();
if((temp.se-temp.fi+1)&1) //奇数
mid=(temp.fi+temp.se)/2;
else
mid=(temp.fi+temp.se-1)/2;
ans[mid]=i;
if(mid>temp.fi)
pq.push(make_pair(temp.fi,mid-1));
if(mid<temp.se)
pq.push(make_pair(mid+1,temp.se));
}
rep(i,1,n+1)
cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}
做的时候想到了是分组来做，但是没想到每一组具体怎么做
其实就是基于一个简单事实，对于一组，如果在i位置上要能是1
那么它前面的肯定要么全是0，要么已经安置好了一段连续的1，于是直接
分组dp,计算答案哪儿还不是特别想明白，还得思考
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j); i<(k); ++i)
#define pb push_back
#define PII pair<int,int>
#define PLL pair<long long, long long>
#define ini(a,j) memset(a,j,sizeof a)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define fi first
#define se second
#define LL long long
#define beg begin()
#define ed end()
#define all(x) x.begin(),x.end()
const int N=1e6+10;
string a;
int solve(string& s){
int cnt=count(s.begin(),s.end(),'1');
int n=s.length();
vector<int> res(n);
int prefix=0;
int ans=cnt;
rep(i,0,n){
int cur=s[i]-'0';
prefix += cur;
//dp[i]=min(dp[i-1],prefix[i-1]) + s[i]!='1'
res[i]='1'-s[i];
if(i>0)
res[i] += min(prefix-s[i]+'0',res[i-1]);
ans = min(ans,res[i]+cnt-prefix);
}
return ans;
}
int main(int argc, char const *argv[])
{
// #define DEBUG
#ifdef DEBUG
freopen("1.dat","r",stdin);
freopen("ans.dat","w",stdout);
#endif
int _;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>_;
while(_--){
int n,k;
cin>>n>>k;
cin>>a;
int cnt=count(all(a),'1');
vector<string> part(k,"");
rep(i,0,n)
part[i%k] += a[i];
int ans= INT_MAX;
for(auto &s:part){
ans = min(ans,solve(s)+cnt-count(all(s),'1'));
}
cout<<ans<<endl;
}
return 0;
}