hihocoder[Offer收割]编程练习赛5及参考

本文主要是介绍hihocoder[Offer收割]编程练习赛5及参考，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1 : 小Ho的防护盾

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho的虚拟城市正在遭受小Hi的攻击，小Hi用来攻击小Ho城市的武器是一艘歼星舰，这艘歼星舰会以T(T为大于0的整数)个单位时间的间隔向小Ho的城市轰击。歼星舰总共有N枚炮弹，其中第i枚会造成Ai点伤害值。

幸好小Ho的城市有K层护盾，每层护盾可以抵挡M点伤害。当某次轰击使得伤害值达或超过M时，该层护盾就会被击碎；该次轰击溢出的伤害不会作用于下一层护盾；下一次轰击将由下一层护盾承受。

同时，受损但尚未被击碎护盾会以每单位时间减少1点伤害值的速度修复自己，直到伤害值降为0。这就意味着小Hi的攻击间隔T越大，小Ho撑过这N枚炮弹的可能性就越大。

那么问题来了，小Hi的攻击间隔T至少需要是多少，小Ho城市的防护护盾才能不被全部击破？

为了使题目不存在歧义，规定：

小Hi的第i次攻击发生在时刻(i-1)*T

小Ho的第i次修复发生在时刻i-0.5

输入
第一行包含3个整数N、M和K，意义如前文所述。

第二行包含N个整数A1 - AN，表示小Hi第i枚炮弹的伤害值。

对于30%的数据，满足N<=100

对于100%的数据，满足1<=N<=100000

对于100%的数据，满足1<=K<=10, 1<=Ai, M<=100000

输出
输出使得小Ho城市的防护护盾不被全部击破的小Hi攻击间隔的最小值。如果不存在这样的T，则输出-1。

样例输入
3 5 1
3 3 3
样例输出
3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int check(int ttime, int n, int m, int k, int* num){int i,j, atk = 0;for(i=0; i<n; i++){atk -= ttime;if(atk < 0){ atk = 0; }atk += num[i];if( atk >= m ){k--;atk = 0;}}if(k > 0){return 1;}else{return 0;}
}int main(){int i,j, n,m,k, ans;scanf("%d %d %d", &n, &m, &k);int* num = (int *)calloc(n+1, sizeof(int));for(i=0; i<n; i++){scanf("%d", &num[i]);}int mid, low = 1, high = m+1;ans = -1;while(low < high){mid = low + (high - low)/2;if(check(mid, n, m, k, num)){ans = mid;high = mid;}else{low = mid + 1;}}printf("%d\n", ans);free(num);return 0;
}

题目2 : 小P的强力值

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi在虚拟世界中有一只小宠物小P。小P有K种属性，每种属性的初始值为Ai。小Ho送给了小Hi若干颗药丸，每颗药丸可以提高小P指定属性1点。通过属性值，我们可以计算小P的强力值=(C1(1/B1))(C2(1/B2))…*(CK(1/BK))，其中Ci为小P第i项属性的最终值（Ai+药丸增加的属性）。已知小Ho送给小Hi的药丸一共有N颗，问小P的强力值最高能够达到多少？

输入
第一行包含两个整数N，K，分别表示药丸数和属性种数。

第二行为K个整数A1 - AK，意义如前文所述。

第三行为K个整数B1 - BK，意义如前文所述。

对于30%的数据，满足1<=N<=10, 1<=K<=3

对于100%的数据，满足1<=N<=100000, 1<=K<=10

对于100%的数据，满足1<=Ai<=100, 1<=Bi<=10

输出
输出小P能够达到的最高的强力值。

只要你的结果与正确答案之间的相对或绝对误差不超过千分之一，都被视为正确的输出。

样例输入
5 2
1 1
3 2
样例输出
2.88

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;int main()
{int n, k;cin >> n >> k;vector<int> a(n), b(n);for (int i = 0; i < k; i++)cin >> a[i];for (int i = 0; i < k; i++)cin >> b[i];for (int i = 0; i < n; i++){double max = 0;int index = 0;for (int j = 0; j < k; j++){double v = (log(a[j] + 1) - log(a[j])) / b[j];if (v > max){max = v;index = j;}}a[index]++;}double v = 0;for (int i = 0; i < k; i++)v += log(a[i]) / b[i];v = exp(v);//cout << v << endl;注意输出精度printf("%.5lf\n",v);return 0;
}

第二思路：

#include <stdio.h>
#include <math.h>#define MAXN 100004int A[MAXN];
int B[MAXN];
int N,K;double f(){double re = 1;for(int i = 0;i<K;i++){double a = A[i];double b = B[i];re *= pow(a,1/b);}return re;
}void F(){for(int i = 0;i<N;i++){double mmax = -1;int mmaxi;for(int j = 0;j<K;j++){A[j]++;double v = f();if(v>mmax){mmax = v;mmaxi = j;}A[j]--;}A[mmaxi]++;}printf("%lf\n",f());
}int main(){while(scanf("%d %d",&N,&K)==2){for(int i = 0;i<K;i++){scanf("%d",&A[i]);}for(int i = 0;i<K;i++){scanf("%d",&B[i]);}F();}return 0;
}

题目3 : 震荡数组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个长度为N的数组A1, A2, …, AN，如果对于任意1 < i < N都有Ai > Ai-1且Ai > Ai+1, 或者Ai < Ai-1且Ai < Ai+1，我们就称A数组是一个震荡数组。

例如{4, 2, 3, 1, 5}就是一个震荡数组；而{1, 4, 3, 2, 5}不是一个震荡数组因为4, 3, 2三个连续的元素不满足条件。

现在给定一个长度为N的数组组A1, A2, …, AN，最少进行多少次两两交换，可以使A变成一个震荡数组？

输入
第一行包含一个整数N，代表数组的长度。(1 <= N < 30)

第二行包含N个整数，A1, A2, … AN。 (1 <= Ai <= N)

输入保证Ai两两不同。

输出
输出最少交换的次数。

样例输入
5
1 2 3 4 5
样例输出
1

#include<iostream>
using namespace std;
#define N 110
int a[N],b[N];
#define inf 0x3f3f3f3f
int n,m,k,ans,min_ans;void print(int *a,int n)
{for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;ans++;
}bool check(int h)
{if(h>1&&h%2==1&&(a[h]-a[h-1])<0)return 1;if(h>1&&h%2==0&&(a[h]-a[h-1])>0)return 1;return 0;
}
void dfs(int n,int h,int z)
{if(h==n+1){min_ans=min(min_ans,z);return ;}if(z>=min_ans) return ;int tmp;if(h>1&&h%2==1&&(a[h]-a[h-1])<0)dfs(n,h+1,z);if(h>1&&h%2==0&&(a[h]-a[h-1])>0)dfs(n,h+1,z);if(h==1)dfs(n,h+1,z);if(z+1>=min_ans) return ;for(int i=h+1;i<=n;i++){if(check(i)==1) continue;tmp=a[h];a[h]=a[i];a[i]=tmp;if(h>1&&h%2==1&&(a[h]-a[h-1])<0)dfs(n,h+1,z+1);if(h>1&&h%2==0&&(a[h]-a[h-1])>0)dfs(n,h+1,z+1);if(h==1)dfs(n,h+1,z+1);tmp=a[h];a[h]=a[i];a[i]=tmp;}}
int main()
{int n;while(cin>>n){for(int i=1;i<=n;i++)cin>>a[i];min_ans=inf;ans=0;dfs(n,1,0);for(int i=1;i<=n;i++)a[i]=-a[i];dfs(n,1,0);cout<<min_ans<<endl;}
}

题目4 : 凸多边形

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个凸多边形的N个顶点。你需要在凸多边形内找到M个点，使得这M个点也围成一个凸多边形，并且围成的面积尽可能大。

输入
第一行包含两个整数N和M，意义如前文所述。

接下来N行，每行两个整数Ai和Bi，表示按照逆时针顺序排列的凸多边形顶点坐标。

对于30%的数据，满足N<=5

对于100%的数据，满足N<=100

对于100%的数据，满足3<=M < N, |Ai|,|Bi|<=10000

输出
输出新凸多边形最大的面积，保留两位小数。

样例输入
4 3
0 0
1 0
1 1
0 1
样例输出
0.50

#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
struct point {int x, y;
};
int n, m;
double ans, an,anss=0;
point p[102];
bool v[102];
vector<int> a;
double area(point a, point b, point c) {return fabs((a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x));}double calc() {double ans = 0;a.clear();for (int i = 0; i < n; i++) {if (v[i]) a.push_back(i);}for (int i = 1; i < a.size() - 1; i++)ans += area(p[a[0]], p[a[i]], p[a[i+1]]);return ans;
}
double calc2() {double ans=0;for (int i = 1; i < a.size() - 1; i++)ans += area(p[a[0]], p[a[i]], p[a[i+1]]);return ans;
}
void dfs(int nn,int mm){if (mm==m){double aa =calc2();if (aa>anss) anss=aa;return;}for (int i=nn;i<n;i++){a.push_back(i);dfs(i+1,mm+1);a.pop_back();}
}
int main() {cin >> n >> m;int x1, x2;for (int i = 0; i < n; i++)cin >> p[i].x >> p[i].y;srand((unsigned) time(NULL));for (int j = 0; j < 1000; j++) {memset(v,0,sizeof(v));for (int i=0;i<m;i++){int x= rand()%n;while (v[x]) x= rand()%n;v[x]=true;}ans = calc();for (int i = 0; i < 1500; i++) {x1 = rand() % n;x2 = rand() % n;while (!(v[x1] ^ v[x2])){x1 = rand() % n;x2 = rand() % n;}v[x1] = !v[x1];v[x2] = !v[x2];an = calc();if (an > ans) ans = an;else {v[x1] = !v[x1];v[x2] = !v[x2];}}        if (ans>anss) anss=ans;}printf("%.2lf\n", anss / 2);
}