如何建立网站和网页/做企业网站建设的公司
2022-03-04每日刷题打卡
代码源——div2每日一题
饿饿 饭饭 - 题目 - Daimayuan Online Judge
有n个同学正在排队打饭，第i个同学排在从前往后第i个位置。但是这天食堂内只有一个食堂阿姨，为了使同学们都能尽快的吃上饭，每一个同学在打完一份饭之后就会排在队伍的末尾先吃着打到的饭，我们知道第i个同学的饭量为ai，也就是说第i个同学要吃ai份饭才能吃饱，当一位同学吃饱后，他就会立刻离开食堂，不会排在队伍的末尾。食堂阿姨想知道，在打完k份饭之后，队伍的样子是怎样的，但是食堂阿姨数学不太好，想让你帮忙想想办法。
输入格式
第一行给出两个整数n，k。
第二行给出n个整数a1,a2,…an
输出格式
如果食堂阿姨打饭数少于k，请输出"-1"。
否则按照队伍顺序输出每一个同学的编号。
样例输入1
3 3
1 2 1
样例输出1
2
用一个map记录所有学生的饭量的出现次数，因为map的自动排序功能，使得小饭量的会排在前面。把学生的饭量按照输入顺序存入数组中，同时记录所有饭量的总和，如果总和小于k，就直接输出-1。开始模拟打饭，每次我们给全体喂当前打饭人中饭量最少的分量，我们直接从map中取出即可，喂完后，饭量最少的人就离开了队伍，我们要准备一个len来记录队伍剩余的人，以此往复，当剩下的饭不够喂满最低饭量的人时结束循环，我们把剩余饭量k对len取余，这样剩下的饭量就只够再打一趟饭了，我们遍历队伍，如果有没吃饱的人就给他一份饭，然后他把存入另一个数组里（这个数组就充当队尾），要注意，如果有人在此过程中吃饱了，就不存入数组里。最后先输出队伍剩余的人，在输出队尾数组里的人。
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<unordered_map>
#include<stack>typedef long long ll;
typedef pair<int, int>PII;int main()
{map<ll, int>mymap;ll n, k;ll sum = 0;cin >> n >> k;vector<ll>v(n + 1);for (int i = 1; i <= n; i++){cin >> v[i];sum += v[i];mymap[v[i]]++;}if (sum < k){cout << -1 << endl;return 0;}ll len = n, res = 0, algo = 0;auto it = mymap.begin();while (it!=mymap.end()&&k >= (it->first - algo) * len){k -= (it->first - algo) * len;len -= it->second;res = it->first;algo = it->first;it++;if (len == 1)cout << " ";}if (len == 0){return 0;}k %= len;int ans = 1;vector<ll>back;bool flag = false;for (int i = ans; i <= n && k; i++){flag = false;if (v[i] == res + 1){k--;ans = i;flag = true;}else if (v[i] > res){back.push_back(i);ans = i;k--;flag = true;}}if (flag)ans++;for (int i = ans; i <= n; i++){if (v[i] > res)cout << i << " ";}for (int i = 0; i < back.size(); i++)cout << back[i] << " ";return 0;
}
力扣——每日一题
2104. 子数组范围和
给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
示例 1：
输入：nums = [1,2,3]
输出：4
解释：nums 的 6 个子数组如下所示：
[1]，范围 = 最大 - 最小 = 1 - 1 = 0
[2]，范围 = 2 - 2 = 0
[3]，范围 = 3 - 3 = 0
[1,2]，范围 = 2 - 1 = 1
[2,3]，范围 = 3 - 2 = 1
[1,2,3]，范围 = 3 - 1 = 2
所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
从大范围到小范围遍历，遍历过程中记录最大值和最小值，并且每次记录最大值与最小值的差值。
class Solution {
public:typedef long long ll;long long subArrayRanges(vector<int>& nums) {ll res=0;int n=nums.size();for(int len=0;len<n;len++){int min_num=1e9,max_num=-1e9;for(int i=len;i<n;i++){min_num=min(min_num,nums[i]);max_num=max(max_num,nums[i]);res+=max_num-min_num;}}return res;}
};