首页 > 代码库 > Codeforces #380 Subordinates(贪心 构造)
Codeforces #380 Subordinates(贪心 构造)
从前往后扫,找到一出现次数为0的数,从后面找一个出现不为0的数转化而来。设置两指针l, r来处理。
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<utility> using namespace std; typedef long long LL; const int N = 1000008, INF = 0x3F3F3F3F; int a[N], cnt[N], rem[N]; int main(){ int n, s; cin >> n >> s; for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); } int ans = 0; if(a[s]){ ans++; a[s] = 0; } for(int i = 1; i <= n; i++){ cnt[a[i]]++; } cnt[n] += cnt[0] - 1; int l = 1, r = n; while(l < r){ while(cnt[l] && l < r){ l++; } while(cnt[r] == 0 && l < r){ r--; } if(l < r){ cnt[l]++; cnt[r]--; ans++; } } cout<<ans<<endl; return 0; }
Codeforces #380 Subordinates(贪心 构造)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。