网站开发技术难度,商丘网站推广渠道,网站手机app开发,深圳市建筑市场信息公开平台开幕式排练
题目描述 导演在组织进行大运会开幕式的排练#xff0c;其中一个环节是需要参演人员围成一个环形。演出人员站成了一圈#xff0c;出于美观度的考虑#xff0c;导演不希望某一个演员身边的其他人比他低太多或者高太多。 现在给出n个参演人员的身高#xff0c;问…开幕式排练
题目描述 导演在组织进行大运会开幕式的排练其中一个环节是需要参演人员围成一个环形。演出人员站成了一圈出于美观度的考虑导演不希望某一个演员身边的其他人比他低太多或者高太多。 现在给出n个参演人员的身高问在他们站成一圈时相邻演员的身高差的最大值至少是多少? 请你帮忙计算。 输入输出描述 输入 输入包括两行第一行有1个正整数代表人数 n。 第二行有n个空格隔开的正整数h表示第i个演员的身高。 输出 输出包括一个正整数表示答案。 样例 输入 5 2 1 1 3 2 输出 1 思路 可以采用贪心的思想将身高从大到小排序从第一个开始轮流放到每两个相邻的队列的两端此种方法可以尽可能使得相邻身高差的最大值最小。 code
#includebits/stdc.husing namespace std;int n, m, k, t;
const int N 1e5 10;
int a[N];int main()
{cin n;for(int i 0; i n; i ) cin a[i];sort(a, a n);dequeintq;bool flg true;for(int i 0; i n; i ){if(flg) q.push_back(a[i]);else q.push_front(a[i]);flg !flg;}int ans abs(q.front() - q.back());for(int i 1; i n; i )ans max(ans, abs(q[i] - q[i - 1]));cout ans \n;return 0;
} 最少数字
题目描述 小明用计算机随机生成了N个正整数他希望从这N个数中选取若千个数使得它们的和等于M。这些随机生成的数字可能会相同但是每个数字最多只允许使用一次。 当然这样的选取方案可能不存在也可能有多个。现在希望你编写一个程序能够找出数字个数最少的选取方案输出对应的最少数字的个数如果无解输出“No solution”。 输入输出描述 输入 单组输入每组输入2行。 第1行包含两个正整数N和M分别表示初始输入的正整数个数和目标数字和(N1e3M1e5)。 第2行为N个正整数两两之间用空格隔开(每一个正整数均小于等于1e5)。 输出 输出数字个数最少的选取方案中所包含的最少数字个数如果无解输出“No solution”。 样例 输入 5 5 1 3 2 1 1 输出 2 思路 典型的背包问题的思路对于每个数字可以有选和不选两种状态。 设定集合d[i, j]的值为在前i个数字中选择合成j的数字数。属性为集合的最小值。 当选择第i个数字时d[i, j] d[i-1, j - v[i]] 1; 当不选择第i个数字时d[i, j] d[i-1, j]。 综上可得d[i, j] min(d[i-1, j-v[i]] 1, d[i-1, j])。 为了降低时间复杂度可以通过滚动数组的思想来进行优化 d[j] min(d[j], d[j - v[i]] 1) code
#includebits/stdc.husing namespace std;int n, m, k, t;
const int N 1e5 10, INF 0x3f3f3f3f;
int a[N], f[N];int main()
{memset(f, 0x3f, sizeof f);cin n m;for(int i 1; i n; i ) cin a[i];f[0] 0;for(int i 1; i n; i )for(int j m; j a[i]; j --)f[j] min(f[j], f[j - a[i]] 1);if(f[m] INF / 2) puts(No solution);else cout f[m] \n;}
