4 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1e7+5; int a[N],cnt[4],b[4]; signed main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; cnt[a[i]]++; } for(int i=1;i<=cnt[1];i++)//第一段 { if(a[i]==1) continue; b[a[i]]++; } for(int i=cnt[1]+1;i<=cnt[1]+cnt[2];i++)//第二段 { if(a[i]==2) continue; b[a[i]]++; } cout<<b[3]+max(b[1],b[2])<<'\n';//前两段出现了3是必须要换的,直接加上;第一段出现了 2,第二段出现了 1,则 b[]较大值为交换次数 return 0; }#include<bits/stdc++.h> using namespace std; const int N=1e7+5; int a[N],cnt[4]; signed main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; cnt[a[i]]++; } int x=0, y=0, ans=0; for(int i=1;i<=cnt[1];i++) if(a[i]==2) x++; for(int i=cnt[1]+1;i<=n-cnt[3];i++) if(a[i]==1) y++; for(int i=n-cnt[3]+1;i<=n;i++) if(a[i]!=3) ans++; cout << ans+max(x,y)*2-min(x,y)-(max(x,y)-min(x,y)) << '\n'; } -
-2
题意
有n个数,其中的数只有1,2,3
可以每次交换任意两个数
问最少换多少次可以使得数组有序
code
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; int a[N], cnt[4], n; void read() { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; cnt[a[i]]++; } return ; } void init() { } void compute() { int ans = 0; //将左右两端不合法的1,3交换 for(int l = 1, r = n; l <= cnt[1] && r >= n - cnt[3] + 1;) { while(a[l] != 3 && l <= n) l++; while(a[r] != 1 && r >= 1) r--; if(l <= cnt[1] && r >= n - cnt[3] + 1) ans++,swap(a[l],a[r]), l++, r--; } //将1摆好 for(int l = 1, r = n; r > l;) { while(a[l] == 1 && l <= n) l++; while(a[r] != 1 && r >= 1) r--; if(l < r) ans++, swap(a[l],a[r]), l++, r--; } //将3摆好 for(int l = 1, r = n; r > l;) { while(a[l] != 3 && l <= n) l++; while(a[r] == 3 && r >= 1) r--; if(l < r) ans++, swap(a[l],a[r]), l++, r--; } cout << ans; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); read(); init(); compute(); return 0; }
- 1
信息
- ID
- 90
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 124
- 已通过
- 16
- 上传者