Codeforces Round #560 (Div. 3)

野性酷女 2021-11-01 04:38 216阅读 0赞

[Codeforces Round \#560 (Div. 3)][Codeforces Round _560 _Div. 3]

#### E. Two Arrays and Sum of Functions ####

## Description ##

You are given two arrays aa and bb, both of length nn.

Let's define a function f(l,r)=∑l≤i≤rai⋅bif(l,r)=∑l≤i≤rai⋅bi.

Your task is to reorder the elements (choose an arbitrary order of elements) of the array bb to minimize the value of ∑1≤l≤r≤nf(l,r)∑1≤l≤r≤nf(l,r). Since the answer can be very large, you have to print it modulo 998244353998244353. Note that you should minimize the answer but not its remainder.

### Input ###

The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of elements in aa and bb.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106), where aiai is the ii-th element of aa.

The third line of the input contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bj≤1061≤bj≤106), where bjbj is the jj-th element of bb.

### output ###

Print one integer — the minimum possible value of  ∑1≤l≤r≤nf(l,r)∑1≤l≤r≤nf(l,r) after rearranging elements of bb, taken modulo 998244353998244353. Note that you should minimize the answer but not its remainder.

### Examples ###

#### Input ####

5  
1 8 7 2 4  
9 7 2 9 3

### Output ###

646

### 正确解法： ###

虽然没看懂题，但是解法是把 c\[i\] = i \*（n-i+1）\*a\[i\] 排序

b\[i\] 排序

ans+=c\[i\]\*b\[n-i+1\];

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# F2. Microtransactions (hard version) #

## Description ##

Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won't start playing until he gets all of them.

Each day (during the morning) Ivan earns exactly one burle.

There are nn types of microtransactions in the game. Each microtransaction costs 22 burles usually and 11 burle if it is on sale. Ivan has to order exactly kiki microtransactions of the ii-th type (he orders microtransactions during the evening).

Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for 11 burle and otherwise he can buy it for 22 burles.

There are also mm special offers in the game shop. The jj-th offer (dj,tj)(dj,tj) means that microtransactions of the tjtj-th type are on sale during the djdj-th day.

Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.

### Input ###

The first line of the input contains two integers nn and mm (1≤n,m≤2⋅1051≤n,m≤2⋅105) — the number of types of microtransactions and the number of special offers in the game shop.

The second line of the input contains nn integers k1,k2,…,knk1,k2,…,kn (0≤ki≤2⋅1050≤ki≤2⋅105), where kikiis the number of copies of microtransaction of the ii-th type Ivan has to order. It is guaranteed that sum of all kiki is not less than 11 and not greater than 2⋅1052⋅105.

The next mm lines contain special offers. The jj-th of these lines contains the jj-th special offer. It is given as a pair of integers (dj,tj)(dj,tj) (1≤dj≤2⋅105,1≤tj≤n1≤dj≤2⋅105,1≤tj≤n) and means that microtransactions of the tjtj-th type are on sale during the djdj-th day.

### output ###

Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.

### Examples ###

#### Input ####

5 6  
1 2 0 2 0  
2 4  
3 3  
1 5  
1 2  
1 5  
2 3

### Output ###

### 正确解法： ###

题目大意是 kk想去买所有她想要的玩具，但她一天只能得到一块钱，一个玩具两块钱。

但是商场有时会打折，在特定天数特定玩具 一块钱。

求kk最早能得到所有她想要玩具的天数。

我感受到了二分的重要之处，枚举 （玩具个数，玩具个数\*2）的天数。

倒着找：在最后一天买了最后一天能打折的玩具，能买多少买多少。

如果买完能打折的玩具后，当天钱 大于等于 当天的话，也就是说没有花，就要去买玩具的原价。因为你在当天 不可能有比当天多的钱。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <cmath>
     5 #include <algorithm>
     6 #include <set>
     7 #include <map>
     8 #include <vector>
     9 #include <cctype>
    10 #include <sstream>
    11 using namespace std;
    12 typedef long long ll;
    13 const int inf=0x7fffffff;
    14 const int N=400000+100;
    15 const int M=50000+10;
    16 const int MOD=998244353;
    17 const double PI=acos(-1.0);
    18 int n,m;
    19 int a[N],b[N];
    20 vector<int>ve[N];
    21 bool check(int x,int y)
    22 {
    23     int re=x,flag=0;
    24     for(int i=1;i<=n;i++)   b[i]=a[i];
    25     for(int i=x;i>=1;i--)
    26     {
    27         for(int j=0;j<ve[i].size();j++)
    28             while(b[ve[i][j]]&&re)
    29             {
    30                 re--;   b[ve[i][j]]--;
    31                 y--;
    32             }
    33         if(re>=i)   {re--;  flag++;}
    34     }
    35     if(flag/2>=y)   return 1;
    36     return 0;
    37 }
    38 int main()
    39 {
    40     int sum=0,ans=inf;
    41     scanf("%d %d",&n,&m);
    42     for(int i=1;i<=n;i++)
    43     {
    44         scanf("%d",&a[i]);
    45         sum+=a[i];
    46     }
    47     for(int i=1;i<=m;i++)
    48     {
    49         int aa,bb;
    50         scanf("%d %d",&aa,&bb);
    51         ve[aa].push_back(bb);
    52     }
    53     int l=sum,r=sum*2;
    54     while(l<=r)
    55     {
    56         int mid=l+r >>1;
    57         if(check(mid,sum))
    58         {
    59             ans=min(ans,mid);
    60             r=mid-1;
    61         }
    62         else    l=mid+1;
    63     }
    64     cout<<l<<endl;
    65 
    66     return 0;
    67 }

![1019034-20190515145248804-71196704.png][]

转载于:https://www.cnblogs.com/Kaike/p/10869428.html

[Codeforces Round _560 _Div. 3]: https://codeforces.com/contest/1165
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/e77595ca478c481ebf76d90e6988b35b.png
[1019034-20190515145248804-71196704.png]: /images/20211101/7743ddc9731d4a368af24aa487af7a78.png