首页 > 其他分享 >YACS 2023年6月月赛 乙组 T3 工作安排 题解

YACS 2023年6月月赛 乙组 T3 工作安排 题解

时间:2023-08-21 10:55:36浏览次数:37  
标签:YACS Node int 题解 乙组 times n1 n2

这道题是乙组里比较新奇的一题,本来一眼看下来不会,后来蒙了个按照单位时间内收到罚款排序居然对了,十分意外。

简单的证明一下:
假设有两个工作,时间分别为 $t_1$ $f_1$ $t_2$ $f_2$,假设把第一个放在前面更优,前面的罚款不变。

则有 $t_1\times f_1+(t_1+t_2)\times f_2<t_2\times f_2+(t_1+t_2)\times f_1$。

化简后可得 $t_1\times f_2<t_2\times f_1$。

进一步移项可得 $\frac{t_1}{f_1}<\frac{t_2}{f_2}$,然后排序即可。

代码很短:

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, s, ans;
struct Node {int x, y;}a[200005];
bool cmp (Node n1, Node n2) {return n1.y * n2.x > n2.y * n1.x;}
signed main () {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
    sort (a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i ++) {
        s += a[i].x;
        ans += s * a[i].y;
    }
    cout << ans;
    return 0;
}

 

标签:YACS,Node,int,题解,乙组,times,n1,n2
From: https://www.cnblogs.com/Xy-top/p/17645436.html

相关文章

  • [2023 上半年] [软件设计师] [下午题] 题解报告
    2023年下午题整体难度有所上升,取消了简单和困难难度,全部设置为中等难度。第一题数据流图随着农业领域科学种植的发展,需要对农业基地及农事进行信息化管理,为租户和农户等人员提供种植相关服务。现欲开发农事管理服务平台,其主要功能是:(1)人员管理。平台管理员管理租户;租户管理农户并......
  • [ABC297G] Constrained Nim 2 题解
    题意有\(N\)堆石子,其中第\(i\)堆有\(A_i\)个石子。每次可以选一堆从中取\(\left[L,R\right]\)个,问判断先手后手胜负。(\(1\leN\le2\times10^5,1\leL\leR\le10^9,1\leA_i\le10^9\))。题解考虑子游戏,即只有一堆石子的情况,考虑其\(\operatorname{SG}\)......
  • CF1823F Random Walk 题解
    题意给定一棵由\(n\)个节点组成的树,定义每次移动的方式为等概率的移动到相邻节点上,询问从\(s\)移动到\(t\)的过程中每个点的期望经过次数。(\(1\len\le2\times10^5\))。题解定义\(f_i\)为节点\(i\)的期望经过次数,\(fa_u\)为节点\(u\)的父亲节点,\(\operatorna......
  • 「TAOI-2」Break Through the Barrier 题解
    前言:比赛前去做牙齿矫正,回来晚了10分钟……做比赛的运气全用在了一路绿灯上了(无语)。第二题切了两个半小时。决定写篇题解来抒发一下再记得愤怒愉悦之情。AC的想法很简单,就是表示出每一串连续的\(\texttt{T}\),其长度分别为\(l_1\liml_m\)。明显的,对于任何一个\(l_i\),在一......
  • P1345 [USACO5.4] 奶牛的电信Telecowmunication 题解
    P1345[USACO5.4]奶牛的电信Telecowmunication题目描述农夫约翰的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由\(c\)台电脑组成的序列\(a_1,a_2,\cdots,a_c\),且\(a_1\)与\(a_2\)相连,\(a_2\)与......
  • P9556 [SDCPC2023] A-Orders 题解
    题目传送门一道模拟题。可以命名一个订单的结构体,然后将订单的结束时间进行排序。用一个变量模拟货物的数量,每遇到一个订单,货物的数量就会加上距离上一个订单的天数乘上\(k\)。即对于第\(i\)个订单,距离第\(i-1\)订单货物数量增加了\((a_{i}-a_{i-1})\timesk\)。如果在模......
  • CSP模拟赛题解
    目录CSP模拟16T1:糖果CSP模拟17T1:弹珠游戏T2:晚会CSP模拟18T1:TheThirdLetterT2:InaoftheMountainCSP模拟19T1:StrangeFunctionT2:DZYLovesModificationCSP模拟21T1:[CEOI2016]kangarooT2:[JOI2023Final]Advertisement2T3:YourCSP模拟22T1:TheChildandToyCSP模拟16T1:......
  • JS习题解析
    1、页面有一个id为button1的按钮,如何通过原生的js禁用?(IE考虑IE8.0以上版本)A、document.getElementById("button1").readonly=true;B、document.getElementById("button1").setAttribute('readonly','true');C、document.getElementById("button1&quo......
  • 题解 Cow and Snacks
    被黄题创死了2333题目链接首先肯定有一个贪心的想法:尽量使得人们拿的花重复,即尽量使得每个人都拿一束花。当然第一个人必须拿两束。接着思考:如何找出有几个人是必须拿两束花的。其实很简单,当\(A,B\)两人不能通过其他人使得他们的花有联系,比如\(A\)喜欢\(1,2\),\(B\)喜欢......
  • 8.20题解
    T1sun暴力枚举即可时间复杂度分析:\((lnx)'=\frac{1}{x}\)根据牛顿-莱布尼茨公式可得:\(\sum_{x=1}^{n}{\frac{1}{x}}=\int_{1}^{n}{\frac{1}{x}}=ln(n)-ln{1}=ln(n)\)令\(ln(n)=k\)可得:\(n=e^{k}<=e^{15}\approx3269017\)T2order首先需要理解题意......