Educational Codeforces Round 3

目录

A. USB Flash Drives

B. The Best Gift

C. Load Balancing

D. Gadgets for dollars and pounds

---

A. USB Flash Drives

#include<bits/stdc++.h>using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;void solve()
{int n,m;cin>>n>>m;vector<int> a(n);for(auto &ai: a) cin>>ai;sort(a.begin(),a.end(),greater<int>() );int cnt=0;int sum=0;for(int i=0;i<n;i++){sum+=a[i];if(sum>=m){cout<<i+1<<endl;return ;}}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

B. The Best Gift

思路：简单组合数学，开个数组记录每个数字出现次数即可。

#include<bits/stdc++.h>using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;void solve()
{int n,m;cin>>n>>m;vector<int >a(n);vector<int> mp(15);for(int i=0;i<n;i++) {cin>>a[i];mp[a[i]]++;}ll ans=0;for(int i=1;i<=10;i++){for(int j=i+1;j<=10;j++){ans+=mp[i]*mp[j];}}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

C. Load Balancing

思路：贪心，我们认为，将每个数转变到平均值附近是最优的，对于余数的处理，若余数为p，平均值为ave，那么我们将数组排序后，最大的p个数转换到ave+1即可。

#include<bits/stdc++.h>using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;void solve()
{int n;cin>>n;vector<ll> a(n);ll sum=0;for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}int avr=sum/n;int p=sum%n;ll res=0;sort(a.begin(),a.end());for(int i=0;i<n;i++){if(i<n-p){res+=abs(avr-a[i]);}else res+=abs(avr+1-a[i]);}cout<<res/2<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

D. Gadgets for dollars and pounds

思路：贪心，二分答案。

对于汇率：若第 i 天的汇率为x，第 i+1 天的汇率为 x+1，那么我们完全可以在第 i 天去购买，又因为题目没有限制一天的购买个数，所以我们完全可以在价格最低的那一天全部买完，我们使用两个数组去分别记录到第 i 天为止，两个汇率的最低价格，由此我们可以知，两个数组维护的值一定是单调递减的，又因为题目要求我们求出最小的天数，所以在这个基础上可以进行二分，我们check对于mid天，我们购买价值前k小的所有物品的总价值是否小于题目给定的价值即可。

#include<bits/stdc++.h>using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> p3;
int mod=998244353;
const int maxv=4e6+5;int n,m,k,s;
vector<pll>a(N),b(N);//维护到第i天为止的最低价格，因为最后要求输出对应购买天数，所以需要用pair
vector<pll> su(N);bool check(int x)//检验前x天的前k小物品的价值总和
{ll res=0;vector<ll> v;for(int i=1;i<=m;i++){auto [c,y]=su[i];if(c==1){v.push_back(a[x].first*y);}else v.push_back(b[x].first*y);}sort(v.begin(),v.end());for(int i=0;i<k;i++){//if(i==k) break;res+=v[i];}return res<=s;
}void solve()
{cin>>n>>m>>k>>s;ll c=2e9,day=1;for(int i=1;i<=n;i++) {int x;cin>>x;if(c>x){c=x;day=i;}a[i]={c,day};}c=2e9,day=1;for(int i=1;i<=n;i++) {int x;cin>>x;if(c>x){c=x;day=i;}b[i]={c,day};}for(int i=1;i<=m;i++){int t,c;cin>>t>>c;su[i]={t,c};}int l=1,r=n;int ans=-1;while(l<=r){//二分答案int mid=(l+r)/2;if(check(mid)){ans=mid;r=mid-1;}else{l=mid+1;}}if(ans==-1){cout<<ans<<endl;return ;}vector<p3> v(m+5);for(int i=1;i<=m;i++){auto [c,y]=su[i];if(c==1){v[i]={a[ans].first*y,i,a[ans].second};}else v[i]={b[ans].first*y,i,b[ans].second};}sort(v.begin()+1,v.begin()+1+m,[](p3 x,p3 y){return x[0]<y[0];});vector<pll> res;for(int i=1;i<=k;i++){auto [x,y,z]=v[i];res.push_back({y,z});}cout<<ans<<endl;for(auto [x,y]: res) cout<<x<<" "<<y<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}