得物（0823笔试）

开幕式排练

时间限制:3000MS 内存限制:655360KB

题目描述:

导演在组织进行大运会开幕式的排练，其中一个环节是需要参演人员围成一个环形。演出人员站成了一圈，出于美观度的考虑，导演不希望某一个演员身边的其他人比他低太多或者高太多。

现在给出n个参演人员的身高，问在他们站成一圈时，相邻演员的身高差的最大值至少是多少? 请你帮忙计算。

输入描述

输入包括两行，第一行有1个正整数，代表人数n。

第二行有n个空格隔开的正整数h表示第i个演员的身高。

数据保证2<=n<=10^5,1<=hi<=10^9。

输出描述

输出包括一个正整数，表示答案。

样例输入

样例输出

思路:注意题目描述需要满足参演人员身边的人身高不要太低或者太高，即包含参演人员左边的人与右边的人与自己的身高差不能太大。于是可以将数组排序，然后声明一个新数组，均匀的向两边插入元素，最后求出相邻演员身高差的最大值。

#include <bits/stdc++.h>
using namespace std;

int main(){
   int n;
   cin>>n;
   vector<int> nums(n);
   for(int i=0;i<n;i++) cin>>nums[i];
   sort(nums.begin(),nums.end());
   vector<int> ans;
   ans.push_back(nums[n-1]);
   int j=0;
   for(int i=n-2;i>=0;i--){
      if(j % 2==0) ans.push_back(nums[i]);
      else ans.insert(ans.begin(),nums[i]);
      j = j^1;     //每次将j在0和1之间取值，方便往数组两边插值
   }
   int maxx=0;
   for(int i=0;i<n;i++)
       maxx=max(maxx,abs(ans[i]-ans[(i+1)%n]));      //注意存在环形队列，即可通过取模的方式实现最后一个元                                                       素与第一个元素的差值计算
   cout <<maxx<< endl;
}

最少数字

小明用计算机随机生成了N个正整数，他希望从这N个数中选取若千个数，使得它们的和等于M。这些随机生成的数字可能会相同，但是每个数字最多只允许使用一次。

当然这样的选取方案可能不存在，也可能有多个。现在希望你编写一个程序，能够找出数字个数最少的选取方案，输出对应的最少数字的个数，如果无解输出“No solution”。

输入描述

单组输入，每组输入2行。

第1行包含两个正整数N和M，分别表示初始输入的正整数个数和目标数字和(N<=1e3,M<=1e5)。

第2行为N个正整数，两两之间用空格隔开(每一个正整数均小于等于1e5)。

输出描述

输出数字个数最少的选取方案中所包含的最少数字个数，如果无解输出“No solution”。

样例输入

样例输出

思路：动态规划，dp[i][j]表示用i个数字能够组成和为j的最小数字个数。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& numbers, int targetSum) {
    int n = numbers.size();
    vector<vector<int>> dp(n + 1, vector<int>(targetSum + 1, INT_MAX / 2));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= targetSum; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= numbers[i - 1]) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - numbers[i - 1]] + 1);
            }
        }
    }

    return (dp[n][targetSum] == INT_MAX / 2) ? -1 : dp[n][targetSum];
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> numbers(N);
    for (int i = 0; i < N; i++) {
        cin >> numbers[i];
    }

    int minCount = solve(numbers, M);

    if (minCount == -1) {
        std::cout << "No solution" << std::endl;
    } else {
        std::cout << minCount << std::endl;
    }

    return 0;
}