2021年暑期训练阶段四Day3
目录
A - Cow Acrobats
B - Dropping tests
C - K Best
D - Pyramid Split
E - Alignment
F - Longest Ordered Subsequence
G - 排序
A - Cow Acrobats
题意：
农夫约翰的N头牛（编号1..N）正计划逃跑加入马戏团。他们有蹄的脚阻止他们走钢丝，也阻止他们在空中荡秋千（他们最后一次试图从大炮里射出一头母牛，结果惨败）。因此，他们决定练习表演杂技特技。
母牛并没有太大的创造力，它们只想出了一个特技：站在彼此的上面，形成一个垂直的高度。奶牛们正试图找出它们在这堆牛中的排列顺序。
每头N头牛都有一个相关的体重（1<=W_i<=10000）和力量（1<=S_i<=100000000）。一头奶牛倒下的风险等于它身上所有奶牛的总重量（当然不包括它自己的体重）减去它的力量（因此一头更强壮的奶牛倒下的风险更低）。您的任务是确定奶牛的顺序，以将任何奶牛的最大崩溃风险降至最低。
思路：
牛有重量和力量两个属性，所以定义一个结构体
对于每头牛而言，应该将他与他上面的所有牛看做一个整体，
则这头牛的危险值为 所有牛的总重-这头牛的重量-这头牛的力量，
要想危险值最小，牛的重量+力量 的值就应该最大。
自定义排序从大到小排序，重量大，力量大的当然在下面。
代码：
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
struct node
{long long w;long long s;
};
int cmp(node a,node b)
{return a.s+a.w>n){for(int i=0; i>cow[i].w>>cow[i].s;sort(cow,cow+n,cmp);long long ans=-inf,temp=0;for(int i=0; ians)ans=temp-cow[i].s;temp+=cow[i].w;}cout< B - Dropping tests
题意：
在某个课程中，你要参加n次测试。如果您在测试i中通过bi问题获得了正确的ai，则您的累积平均值定义为
.
给出你的考试分数和一个正整数k，如果你被允许降低任何k分，确定你的累积平均分有多高。假设你参加了3次考试，分数分别为5/5、0/1和2/6。如果不放弃任何考试，你的累积平均分数为
。但是，如果您放弃第三次测试，您的累积平均值将变为
思路：
二分先枚举 mid ，然后 根据 a[i]-mid*b[i]，从大到小排序，选出要拿的物品。结果大于等于0就可行。
代码：
#include
#include
#include
#define eps 1e-7
using namespace std;int main()
{int n,m;while(~scanf("%d%d",&n,&m)){if(n==0&&m==0)break;double a[2000],b[2000],d[2000];for(int i=0; ieps){mid=(r+l)/2;for(int i=0; i0)l=mid;elser=mid;}printf("%.0f\n",mid*100);//注意输出double时用%f，四舍五入保留小数就直接%.0f!!!}return 0;
}
C - K Best
题意：
德米有许多珠宝。她的每一件珠宝都有一定的价值和重量。
自从她的丈夫约翰在最近的金融危机后破产后，德米决定卖掉一些珠宝。她决定把最好的珠宝留给自己。她决定保留这些珠宝，使它们的具体价值尽可能大。也就是说，表示某组宝石的特定值={i1，i2，…，ik} 如
Demy希望选择其特定价值最大的k珠宝。帮助她这样做。
思路：
二分查找所有可能得到的价值，从中找出最大的价值
由于珠宝的有很多属性并所以定义结构体以及自定义排序。
代码：
#include
#include
#include
#define N 100005
#define MAX 0x3f3f3f3f
using namespace std;
int n,k;
struct node
{double v,w,tcmp;int id;
} a[N];
bool cmp(node n1,node n2)
{return n1.tcmp>n2.tcmp;
}
bool judge(double x)
{double ans=0;for(int i=0; i=0;
}
int main()
{while(~scanf("%d%d",&n,&k)){for(int i=0; i=1e-8){mid=(maxx+minn)/2;if(judge(mid))minn=mid;elsemaxx=mid;}for(int i=0; i D - Pyramid Split
题意：
给一些底面为正方形的锥体，现在要横切这些锥体，即给一个平面，使得这些锥体一分为二，上面部分体积为总体积的一半，问这个平面的高度应该为多少。
思路：
二分平面的高度。当体积为总体积的一半时即可跳出。注意有可能平均高度大于个别比较低的锥体，这个时候对这个锥体分割所得的体积就是0.
代码：
#include
#include
#include
#include
#define eps 0.0000000001
using namespace std;
double V;
int n;
double a[10005],b[10005],h[10005],sum;
double cal(double h,double a,double b)
{if(h>=a)return 0; //如果当前高度大于这个锥体的高度，就是这个锥体没有被分割，体积就是0.double ans,d;d=b*(a-h)/a;ans=d*d*(a-h)/3;return ans;
}
double erfen(double l,double r)
{double x=r;double d,v,mid;int f=0;while(fabs(l-r)>eps){v=0;mid=(l+r)/2;for(int i=1; i<=n; i++)v+=cal(mid,a[i],b[i]); //计算体积if(fabs(2*v-sum)sum)l=mid;}return l;
}
int main()
{int T,k;scanf("%d",&T);while(T--){sum=0;scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%lf",&a[i]);for(int i=1; i<=n; i++)scanf("%lf",&b[i]);for(int i=1; i<=n; i++){V=1.0/3*a[i]*b[i]*b[i];sum+=V; //总体积}double x=erfen(0,100000);printf("%d\n",(int)x); //取整}return 0;
}
E - Alignment
题意：
给出一列队伍中的人的身高，让队伍中一些人离开，使得留下的每个人至少能从一边看到无穷远处
思路：
注意中间两人身高可以相等
保持从前面往后面是递增的，从后面往前面是递增的即可，即至多有一个极值。
代码：
#include
#include
#include
using namespace std;
int l[1010],r[1010];
double a[1010];
int sum,ans;
int main()
{ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)//求从前往后包含a[i]的最长递增序列长度{l[i]=1;for(int j=1;j=1;i--)//求从后往前包含a[i]的最长递增序列长度{r[i]=1;for(int j=n;j>i;j--){if(a[j] F - Longest Ordered Subsequence
题意：
如果a1
思路：
dp经典题型，dp数组记录当前最长子序列的长度，边输入边判断，
伪状态转移方程：dp[i]=dp(之前的比 i 小的而且dp值最大的)+1;
代码：
#include
#include
#include
using namespace std;
int a[1003];
int dp[1003];
int main()
{ios::sync_with_stdio(false);int n;while(cin>>n){int ans=0;for(int i=1;i<=n;i++){cin>>a[i];int t=0;for(int j=1;jt)t=dp[j];}dp[i]=t+1;if(dp[i]>ans)ans=dp[i];}cout< G - 排序
题意：
输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。
你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。
思路：
模拟排序，注意用scanf，不然会T
代码：
#include
#include
#include
#include
using namespace std;
char s[1010];
int a[1010];
int main()
{ios::sync_with_stdio(false);while(cin>>s){memset(a,0,sizeof(a));int cnt=0;int l=strlen(s);s[l]='5';//cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！