鏈接:http://codeforces.com/contest/1118
來源:Codeforces

---

文章目錄

• A. Water Buying
• B. Tanya and Candies(前綴和)
• D1. Coffee and Coursework (Easy version)(貪心)
• D2. Coffee and Coursework (Hard Version)(二分)

---

A. Water Buying

??題意:用最小的花費買到剛好合適的東西.我們可以求出兩種方案的花費,最后輸出最小的即可.

#include<cstdio> #include<cstdlib> #include<iostream> #include<cmath> #include<cstring> #include<string> #define pi 3.1415926 #define mod 1000000007 #include<algorithm> using namespace std;typedef long long LL; const int Max_n=100005; LL a[Max_n];int main(){int t;scanf("%d",&t);while(t--){LL n,a,b;scanf("%lld%lld%lld",&n,&a,&b);LL res,res1;if(n&1) res=a+(n-1)/2*b;else res=n/2*b;res1=n*a;printf("%lld\n",res>res1?res1:res);} return 0; }

---

B. Tanya and Candies(前綴和)

??題意:給你一個數組,刪除其中一個元素,剩下的元素奇數位和偶數位的元素和相等,問這樣的元素有多少個.我們可以用兩個數組分別維護奇數位和偶數位的前綴和,當我們將某一個元素刪除時,前面的不變,后面的位置奇偶互換.此時奇數和就是:sum1[i-1]+sum2[n]-sum[i](sum保存的分別是奇數和與偶數和),偶數和就是:sum2[i-1]+sum1[n]-sum1[n]-sum1[i]

#include <iostream> #include <cstdio> #include <algorithm> using namespace std;typedef long long LL; const int Max_n=200005; int sum1[Max_n],sum2[Max_n],a[Max_n];int main() {int n;scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);if(i&1){sum1[i]=sum1[i-1]+a[i];//奇數和sum2[i]=sum2[i-1];//偶數和}else{sum1[i]=sum1[i-1];sum2[i]=sum2[i-1]+a[i];}}int ans=0;for(int i=1;i<=n;++i){int sumj,sumo;sumo=sum2[i-1]+sum1[n]-sum1[i];sumj=sum1[i-1]+sum2[n]-sum2[i];if(sumj==sumo) ans++;}printf("%d\n",ans);return 0; }

---

D1. Coffee and Coursework (Easy version)(貪心)

C. Magic Ship(二分天數):https://blog.csdn.net/qq_42217376/article/details/87895706
??題意:有一個作業需要寫m頁,你有很多杯咖啡(一組數據),數值就代表喝一杯咖啡能夠寫多少頁作業,在某一天你可以選擇喝任意杯咖啡,但是當天的第一杯咖啡的貢獻值是max(0,a1),第二杯就變成了max(0,a2-1),第三杯是max(0,a3-2),貢獻值依次類推,讓我們求最少多少天可以完成這些作業.上次寫船那道題有一個奇特的想法那就是二分天數來找到最優解.這里我們可以枚舉天數來找到最優解.(二分方法見下題.)

#include <iostream> #include <cstdio> #include <algorithm> using namespace std;typedef long long LL; const int Max_n=200005; int a[Max_n];int main() {int n,m,sum=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){scanf("%d",&a[i]);sum+=a[i];}if(sum<m){printf("-1\n");return 0;}sort(a+1,a+n+1,greater<int>());for(int days=1;days<=n;++days){//枚舉天數int ans=0,cnt=0,b=0;for(int i=1;i<=n;i++){ans+=(a[i]-cnt);//假設我們當前有兩天,我們把數組分成2組(貪心的規則去分組),計算出每組的和,最后找到最合適的天數.if(i%days==0) cnt++;if(ans>=m){b=1;break;}}if(b){printf("%d\n",days);break;}}return 0; }

---

D2. Coffee and Coursework (Hard Version)(二分)

??題意同上題相同,只不過這里數據范圍變了,我們沒辦法在使用枚舉來求解這道題,此時就用到二分天數來求解.

#include <iostream> #include <cstdio> #include <algorithm> using namespace std;typedef long long LL; const int Max_n=200005; int a[Max_n],m,n;bool check(int mid){LL sum=0;for(int i=0,days=0;i<n;i++){sum+=max(0,a[i]-days);if((i+1)%mid==0) days++;}return sum>=m; }int main() {scanf("%d%d",&n,&m);for(int i=0;i<n;++i)scanf("%d",&a[i]);sort(a,a+n,greater<int>());int l=1,r=Max_n,days=0;while(l<=r){int mid=l+((r-l)>>1);if(check(mid)){r=mid-1;days=mid;}else l=mid+1;}printf("%d\n",days?days:-1);return 0; }

轉載于:https://www.cnblogs.com/zut-syp/p/10543669.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Codeforces Round #540 (Div. 3)(部分题解)的全部內容，希望文章能夠幫你解決所遇到的問題。

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