傳送門
題意：一個人有n個程序，每個程序都有占的緩存和價值。現在要釋放m及以上的緩存，求失去的價值的最小值。

題解
首先我們知道如果所有緩存加起來 < m 的話，直接輸出 - 1 就行啦。
其次呢，我們發現價值只有1和2兩個值，如果把兩個價值分開來看，顯然選擇同價值中占緩存多的最優。那么我們首先把他們各自按照緩存從大到小排個序，讓后枚舉價值為 1 的，記錄前綴和為s，那么只需要在另一個數組里 lower_bound 一下 m - s 在哪里即可。
這樣看來這個題是老經典模型啦，可能是這幾天天天擺爛沒看出來。

代碼寫的時候有點混亂，僅供參考。。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; vector<int>a,b; int pre1[N],pre2[N]; struct Node {int a,b; }node[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; cin>>_;while(_--){a.clear(); b.clear();scanf("%d%d",&n,&m);for(int i=0;i<=n+1;i++) pre1[i]=pre2[i]=0;LL s=0;for(int i=1;i<=n;i++) scanf("%d",&node[i].a),s+=node[i].a;for(int i=1;i<=n;i++){scanf("%d",&node[i].b);if(node[i].b==1) a.pb(node[i].a);else b.pb(node[i].a);}if(s<m) { puts("-1"); continue; }sort(a.begin(),a.end()); sort(b.begin(),b.end(),greater<int>());for(int i=0;i<b.size();i++) pre2[i+1]=pre2[i]+b[i];pre2[0]=-INF; pre2[b.size()+1]=INF;n=a.size();int ans=INF; a.pb(0);int sum=0;for(int i=n;i>=0;i--){sum+=a[i];if(sum>m) break;if(sum==m){ans=min(ans,n-i);break;}int rest=m-sum;int pos=lower_bound(pre2+1,pre2+1+(int)b.size(),rest)-pre2;if(pos==(int)b.size()) continue;ans=min(ans,n-i+pos*2);}printf("%d\n",ans);}return 0; } /**/ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF 1475 D. Cleaning the Phone 思维模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。