Codeforces Round #568 (Div. 2)C2. Exam in BerSU (hard version)

貪心+暴力

大致題意：N個(gè)人考試，每個(gè)人花費(fèi)的時(shí)間是a[i]，他們總共花費(fèi)的時(shí)間不能超過(guò)M，求如果第i個(gè)人想要完成考試的話前面最少得多少個(gè)人不能考試

一開(kāi)始拿到題以為是優(yōu)先隊(duì)列，然后不斷暴力前綴和，發(fā)現(xiàn)這樣如果還是復(fù)雜度有O（n^2×logn）2e5的數(shù)據(jù)……自閉…… 后來(lái)才發(fā)現(xiàn)原來(lái)時(shí)間數(shù)據(jù)最大也就100,可以用一個(gè)flag數(shù)組記錄下花費(fèi)時(shí)間x一共有多少個(gè)人，從大到小暴力減到小于等于M為止

我處理的方式可能有些不同，理解一下為什么不是m而是m-x

AC代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<queue> #include<map> #define ll long long #define pb push_back using namespace std; const int maxn=2e5+7; const int MAX_N=109; int ans[maxn]; int flag[MAX_N];int main() {int n,m,sum=0,x;cin>>n>>m;for (int i=0;i<n;i++){scanf("%d",&x);if (sum<=m-x)ans[i]=0;else{int sum1=sum;int num=0;for (int j=100;j>=1;j--){if (sum1-flag[j]*j<=m-x){if ((sum1-m+x)%j==0) num+=(sum1-m+x)/j;else num+=((sum1-m+x)/j)+1;ans[i]=num;break;}else{sum1-=flag[j]*j;num+=flag[j];if (sum1<=m-x){ans[i]=num;break;}}}}sum+=x;flag[x]++;//放在最后的原因是：放前面可能會(huì)把flag[x]減成0，那就相當(dāng)于還是沒(méi)能參加考試}for (int i=0;i<n;i++)cout<<ans[i]<<" ";cout<<endl;return 0; }

七夕快樂(lè)！
（愿天下有情人終成兄妹（^__0

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #568 (Div. 2)C2. Exam in BerSU (hard version)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。