本文主要是介绍C - Job Interview,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:
先不考虑溢出,将n+m+1按照分配的工作分类
会发现,有且仅有一种工作的人数是溢出的,即超过了上限,记作工作1;且另一种工作的人数没有溢出,记作工作2
工作2因为没有溢出,不管没来的那个人是谁,工作2的人还是做工作2,不受影响
工作1溢出了,若没来的那个人在工作1前n个位置,答案是工作1前n+1个人做工作1+其他人做工作2-没来的那个人做工作1;
其他情况答案是前n个人做工作1+其他人做工作2-没来的那个人做工作2
代码:
void solve(){int n,m;cin>>n>>m;int k=n+m+1;vector<int>a(k),b(k);for(int i=0;i<k;i++) cin>>a[i];for(int i=0;i<k;i++) cin>>b[i];vector<int>f(k);vector<vector<int>>p(2);for(int i=0;i<k;i++){if(a[i]>b[i]){f[i]=0;p[0].push_back(i);} else{f[i]=1;p[1].push_back(i);} }if(p[0].size()<=n){swap(n,m);swap(a,b);swap(p[0],p[1]);for(int i=0;i<k;i++) f[i]^=1;}ll s1=0,s2=0;for(int i=0;i<n;i++){int j=p[0][i];s1+=a[j];}for(int i=n;i<p[0].size();i++){int j=p[0][i];s1+=b[j];}for(auto j:p[1]){s1+=b[j];}s2=s1+a[p[0][n]]-b[p[0][n]]; //s1是前n个人工作1,后m+1个人工作2,s2是前前n + 1个人工作1,后m个人工作2vector<ll>ans(k);int cnt=0;for(int i=0;i<k;i++){if(f[i]==0&&cnt<n) ans[i]=s2-a[i];else ans[i]=s1-b[i];if(f[i]==0) cnt++;}for(auto x:ans){cout<<x<<' ';}cout<<'\n';
}
这篇关于C - Job Interview的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!