Educational Codeforces Round 3
A. USB Flash Drives
降序排序后，贪心，甚至不会爆longlong
void solve()
{
int n,m;
cin>>n>>m;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
sort(all(a));reverse(all(a));
int s=0,ans=0;
for(int i=0;i<n;i++)
{
if(s>=m) break;
s+=a[i],ans++;
}
cout<<ans<<endl;
return;
}
B. The Best Gift
大意：有多少种互不相同不同的组合
用map记录这个类型出现的次数
一本书的贡献为 与这本书不同类型的数量
void solve()
{
int n,m;
cin>>n>>m;
LL ans=0,s=0;
vector<int> a(n);
map<int,int> mp;
for(int i=0;i<n;i++)
{
cin>>a[i];
mp[a[i]]++;
s++;
}
for(auto it:mp)
{
ans+=(it.se*(s-it.se));
}
cout<<ans/2ll<<endl;
return;
}
C. Load Balancing
大意:求让最大值和最小值的差最小的操作次数
对数组进行排序，使之升序
\(s\) 为所有数之和，\(k\) 代表平均数，\(r\) 代表余数
$k = \frac{s}{n} $, $ r =s\%n $
当 $ r=0 $ ，最大值和最小值的差为 \(0\)，答案即为\(\sum_{i=1}^n \max(a_i-k,0)\)
当 $ r=1 $ ，最大值和最小值的差为 \(1\)，答案即为\(\sum_{i=1}^{n-r} \max(a_i-k,0)+\sum_{i=n-r+1}^{n} \max(a_i-k-1,0)\)
LL a[N],b[N];
void solve()
{
LL n;
cin>>n;
LL ans=0,s=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s+=a[i];
}
sort(a+1,a+1+n);
LL k=s/n,r=s%n;
for(int i=1;i<=n;i++)
b[i]=k;
for(int i=n;i>=n-r+1;i--)
{
b[i]++;
}
for(int i=1;i<=n;i++)
ans+=max(a[i]-b[i],0ll);
cout<<ans<<endl;
return;
}
D. Gadgets for dollars and pounds
二分，前缀和，贪心
大意：在 \(n\) 天中买东西，每天有不同的汇率，\(m\) 个商品，只能使用pounds或dollars，要买 \(k\) 个，但只有 \(s\) 元钱，判断能不能买，能输出哪天能买完，和哪一天买第几个商品
在 \(1,...,n\) 天中，若第 \(x\) 天能买完 \(k\) 个，那 第 \(k+1\) 天也能买完，也就是在 \(1,...,n\) 天中找到最小满足条件的 \(x\)，且第 \(x-1\) 天不能买完，这是有单调性的，所以我们二分哪天能买完
check中，在 \(1,...,x\) 天中找到最小pounds和dollars的汇率分别是\(a1\) 和 \(b1\)，设消费为 \(sum\) 。题目并没有限制每天购买商品的数量，我们等到汇率最小那天买完是最划算的贪心
这里就有一个问题，如何去确定换了前去买用pounds，还是用dollars的？
因为买\(k\) \((1 ≤ k ≤ 2·10^5)\) 个商品，可以对pounds，和dollars进行排序，用前缀和处理
\(sum=s1[x]·a1+s2[y]·b1\) \((0 ≤ x ≤ \text{pounds商品个数},0 ≤ y ≤ \text{dollars商品个数},x+y=k)\),运用前缀和就可以在\(O(k)\)的时间内处理出第 \(x\) 天结束的最小花销
剩下的输出方案,记录下最小花销下的 \(x\) 、 \(y\) 和 pounds和dollars 汇率最小的日子就很容易解决了
代码有点丑QAQ
const int N = 200010;
LL n,m,k,s,a[N],b[N];
int id,d1,d2;
LL cnt1=0,cnt2=0,s1[N],s2[N];
PII c1[N],c2[N];
bool check(LL x)
{
LL a1=1e18,b1=1e18;
for(int i=1;i<=x;i++)
{
if(a[i]<a1)
d1=i,a1=a[i];
if(b[i]<b1)
d2=i,b1=b[i];
}
LL sum=1e18;
for(int i=0;i<=k;i++)
{
if( !(i<=cnt1&&k-i<=cnt2)) continue;
LL t1=s1[i],t2=s2[k-i];
LL r1=t1*a1,r2=t2*b1;
if(r1+r2<sum)
sum=r1+r2,id=i;
}
if(sum<=s) return true;
else return false;
}
void solve()
{
cin>>n>>m>>k>>s;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=m;i++)
{
LL t,cc; cin>>t>>cc;
if(t==1) c1[++cnt1].fi=cc,c1[cnt1].se=i;
else
c2[++cnt2].fi=cc,c2[cnt2].se=i;
}
sort(c1+1,c1+1+cnt1);
sort(c2+1,c2+1+cnt2);
for(int i=1;i<=cnt1;i++)
s1[i]=s1[i-1]+c1[i].fi;
for(int i=1;i<=cnt2;i++)
s2[i]=s2[i-1]+c2[i].fi;
if(check(n)==false)
{
cout<<-1<<endl; return;
}
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(l))
{
cout<<l<<endl;
vector<PII> ans;
int j=0;
for(int i=1;i<=id;i++)
ans.pb({d1,c1[++j].se});
j=0;
for(int i=id+1;i<=k;i++)
ans.pb({d2,c2[++j].se});
for(auto &it:ans)
cout<<it.se<<" "<<it.fi<<endl;
}
return;
}
