鏈接: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;
}
)
區別)
