首页 > 代码库 > BestCoder#3
BestCoder#3
1001:Task schedule
思路:二分空余时间,注意二分的边界。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> using namespace std; const int maxn =200000+10; int n,m; vector<int> frees; bool have[maxn]; int main(){ int ncase; cin >> ncase; while(ncase--){ scanf("%d%d",&n,&m); frees.clear(); int maxt = 0; memset(have,0,sizeof have); for(int i = 0; i < n; i++){ int t; scanf("%d",&t); maxt = max(maxt,t); have[t] = 1; } for(int i = 1; i < maxn; i++){ if(!have[i]) frees.push_back(i); } while(m--){ int t; scanf("%d",&t); printf("%d\n",*(lower_bound(frees.begin(),frees.end(),t))); } } return 0; }
1002:BestCoder Sequence
题意:让你从1~n的一个全排列中找出中位数为m的字串。
思路:先找出中位数的下标mid,分类讨论(下标):1, 1~mid-1 2,mid+1~n 3.x~mid~y(统计比中位数大的数的个数和比中位数小的数的个数差值)
累加即可。
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> using namespace std; const int maxn = 40000+10; int n,m; int num[maxn]; int cnt[2*maxn],cnt1[2*maxn]; int main(){ while(~scanf("%d%d",&n,&m)){ memset(cnt,0,sizeof cnt); memset(cnt1,0,sizeof cnt1); int mid; for(int i = 1; i <= n; i++){ scanf("%d",&num[i]); if(num[i]==m) mid = i; } int bf = 0; long long ans = 1; for(int i = mid-1; i >= 1; i--){ if(num[i] > num[mid]){ bf++; cnt[bf+maxn]++; }else{ bf--; cnt[bf+maxn]++; } } ans += cnt[maxn]; int bef = 0; for(int i = mid+1; i <= n; i++){ if(num[i] > num[mid]){ bef++; cnt1[bef+maxn]++; ans += cnt[maxn-bef]; }else{ bef--; cnt1[bef+maxn]++; ans += cnt[maxn-bef]; } } ans += cnt1[maxn]; cout<<ans<<endl; } return 0; }
1004:Problem about GCD
题意:计算1~N 与N互质的数的乘积模上N的值
思路:打表发现规律,当N = 2*p^x 或者 p^x是答案为N-1 否则为1(要用大素数测试)
代码不会写,待补。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。