这一场的题目好长啊 D题目都看不懂所以就剩ABC
A
n m n个分数 分数最高为m 最少加上多少个分数 使得平均分能到最高 四舍五入直接模拟就行
#include <iostream> #include <cstdio> using namespace std; int main() { int n,k; scanf("%d%d",&n,&k); double sum=0; for(int i=1;i<=n;i++) { int a; scanf("%d",&a); sum=sum+a; } int i=0; while(1) { if(sum/(n+i)>=k-0.5) break; sum=sum+k; i++; } printf("%d ",i); return 0; }
B
n m 然后n天 分别是每天准备的衣服的数目 然后别人要购买的数目 然后可以挑出m天 使得这m天准备的衣服加倍 问 最多能卖多少衣服
那么贪心 假设是 a b 如果a>=b 那么这一天基本上是不会选的 然后就讨论 a<b
1 a*2>b b-a
2 a*2<b 选的贡献分别是 a 所以按照贡献排序即可
#include <iostream> #include <cstdio> #include<algorithm> using namespace std; #define ll __int64 #define MAXN 100100 struct node { ll a,b; }z[MAXN]; bool cmp(node a,node b) { ll ans1,ans2; if(a.a>=a.b) return 0; if(b.a>=b.b) return 1; if(a.a*2>=a.b) ans1=a.b-a.a; else ans1=a.a; if(b.a*2>=b.b) ans2=b.b-b.a; else ans2=b.a; return ans1>ans2; } int main() { int n,f; while(scanf("%d%d",&n,&f)!=EOF) { for(int i=1;i<=n;i++) scanf("%I64d%I64d",&z[i].a,&z[i].b); sort(z+1,z+n+1,cmp); ll ans=0; for(int i=1;i<=f;i++) ans=ans+min(z[i].a*2,z[i].b); for(int i=f+1;i<=n;i++) ans=ans+min(z[i].a,z[i].b); printf("%I64d ",ans); } return 0; }
C
n 然后n个数 让你列举他的子集 求子集中最大数和最小数的差 然后求和
这种题目 显然是要求每个数的贡献的 那么先拍一下序 比如说 4 3 2 1
那么要算3的正的贡献 最大 那么就是 2^2-1 4有点特殊
3的负的贡献 最小 1^2-1 就是取和不取
#include <iostream> #include <cstdio> #include<algorithm> using namespace std; #define ll __int64 #define MAXN 300100 #define inf 1000000007 ll z[MAXN]; ll x[MAXN]; ll y[MAXN]; bool cmp(ll a,ll b) { return a>b; } ll Quick(ll a,ll b,ll c) { ll ans=1; while(b>0) { if(b&1) ans=(ans*a)%c; b>>=1; a=(a*a)%c; } return ans; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%I64d",&z[i]); ll ans=0; sort(z+1,z+n+1,cmp); for(int i=1;i<=n;i++) { ans=(ans+(z[i]*(Quick(2,n-i,inf)-1))%inf+inf)%inf; ans=(ans-(z[i]*(Quick(2,i-1,inf)-1))%inf+inf)%inf; } printf("%I64d ",ans); return 0; }