Codeforces Round #510 (Div. 2)

A. Benches
题意：公园一共有N个长椅，每个椅子上有Ai个人，后面会新来M个人，问你当M个人坐下以后人数最多的长椅上可以存在的最小人数和最大人数
题解：将每个长椅上的人数塞进一个优先队列，然后每次从优先队列里面取出人数最少的长椅坐一个人上去，最后得到的最大的长椅人数就是可能存在的最小值，而最大值直接就是人数最多的长椅人数加M

#include <bits/stdc++.h>

using namespace std;

int N,M,ans;

priority_queue<int>Q1;
priority_queue<int>Q2;

int main()
{
    scanf("%d %d",&N,&M);
    int v;
    for(int i =1;i <= N;i++){
        scanf("%d",&v);
        Q1.push(v);
        Q2.push(-v);
        ans = max(ans,v);
    }
    
    for(int i = 1;i <= M;i++){
        v = -Q2.top();Q2.pop();v++;
        Q2.push(-v);
        ans = max(v,ans);
    }
    
    printf("%d %d\n",ans,Q1.top()+M);
    
    return 0;
} 

B. Vitamins
题意：有N种药物，每一个的价格为ci，可以补充营养的种类为Si
题解：将每种药物最便宜的找出来，然后将所有药物组合计算一下

#include <bits/stdc++.h>

const int MAXN = 10000,INF = 1000000;

using namespace std;

int n,ans = INF;

map<string,int>mp;

int  main()
{
    int v;string s;
    scanf("%d",&n);
    
    mp["A"] = INF;
    mp["B"] = INF;
    mp["C"] = INF;
    mp["AB"] = INF;
    mp["BC"] = INF;
    mp["AC"] = INF;
    mp["ABC"] = INF;    
    for(int i = 1;i <= n;i++){
        scanf("%d",&v);
        cin>>s;
        sort(s.begin(),s.end());
        mp[s] = min(mp[s],v);                
    }
    
    ans = min(ans,mp["A"]+mp["B"]+mp["C"]);
    
    ans = min(ans,mp["AB"]+mp["C"]);
    ans = min(ans,mp["AC"]+mp["B"]);
    ans = min(ans,mp["BC"]+mp["A"]);
    
    ans = min(ans,mp["AB"]+mp["BC"]);
    ans = min(ans,mp["AC"]+mp["BC"]);    
    ans = min(ans,mp["AB"]+mp["AC"]);
        
    ans = min(ans,mp["ABC"]);
    if(ans == INF) printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}

C. Array Product
题意：给你一个长度为N的数列，你可以选择将任意两个数相乘并保留其中一个，或者是在任何时间删除其中的一个数值（只能删除一次或者是不删除）
题意：模拟，用set将位置存储在一起，先将所有的0和正数乘到一起，如果有奇数个负数那就把最大的负数和0乘到一起然后删除，否则直接把0删除，注意：不存在正数的情况。我太菜了。。。代码好长

#include <bits/stdc++.h>

using namespace std;

#define ps push 
#define mp make_pair
typedef pair<int,int> PII;

int n,suma,sumb,sumc;

PII it;
priority_queue<PII>a,b,c;

int main()
{
    scanf("%d",&n);
    int u,v;
    for(int i = 1;i <= n;i++){
        scanf("%d",&v);
        if(v > 0) {
            a.ps(mp(v,i));
            suma++;
        }
        if(v == 0){
            b.ps(mp(v,i));
            sumb++;            
        }
        if(v < 0){
            c.ps(mp(v,i));
            sumc++;            
        }
    }
    
    while(sumb > 1){ //留一个0 
        it = b.top();b.pop();sumb--;u = it.second;
        it = b.top();v = it.second;
        printf("1 %d %d\n",u,v);
    }
    
    if(sumb == 1 && suma == 0 && sumc == 0) return 0;
    
    while(suma > 1){//留一个正数 
        it = a.top();a.pop();suma--;u = it.second;
        it = a.top();v = it.second;
        printf("1 %d %d\n",u,v);
    }
    
    if(suma == 0 && sumc == 1){
        it = b.top();u = it.second;
        it = c.top();v = it.second;
        printf("1 %d %d\n",u,v);
        return 0;        
    }
    
    if(sumb && sumc & 1){
        it = b.top();b.pop();sumb--;u = it.second;
        it = c.top();c.pop();sumc--;v = it.second;
        printf("1 %d %d\n",u,v);
        printf("2 %d\n",v);
    }
    else if(sumb && !(sumc & 1)){
        it = b.top();b.pop();sumb--;v = it.second;
        printf("2 %d\n",v);
    }
    else if(sumb == 0 && sumc & 1){
        it = c.top();c.pop();sumc--;v = it.second;
        printf("2 %d\n",v);        
    }
    
    if(suma && sumc){
        it = a.top();a.pop();suma--;u = it.second;
        it = c.top();v = it.second;
        printf("1 %d %d\n",u,v);    
    }
    while(sumc > 1){
        it = c.top();c.pop();sumc--;u = it.second;
        it = c.top();v = it.second;
        printf("1 %d %d\n",u,v);    
    }
    return 0;
} 

D. Petya and Array
题意：给你n个数，问有多少个区间的和的值小于t
题解：
sum[i]代表前i个数的和
那么题目表达为：存在多少个0<=k<i使得sum[i]-t<sum[k]
需要注意的是上面的K是从0开始求的，定义sum[0]=0;而sum[i]-sum[0]=sum[i];这样的意义在于将当前点前缀和统计进去
所以直接按权值建线段树统计使上式成立的K的数量，但是因为sum可能很大，故需要离散化

#include <bits/stdc++.h>

const long long MAXN = 1000000;

using namespace std;

int x;
long long n,t,top,ans,a;
long long sum[MAXN],Hash[MAXN],data[MAXN],tmp;

inline long long read(){
    long long x = 0,f = 1;char ch = getchar();
    while(ch < '0' || '9' < ch){if(ch == '-')f = -1;ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x*f;
} 

inline void init()
{
    n = read();t = read();
    for(int i = 1;i <= n;i++) data[i] = read();
    for(int i = 1;i <= n;i++){
        Hash[i] = Hash[i-1] + data[i];
    }
    sort(Hash+1,Hash+n+2);
    top = unique(Hash+1,Hash+n+2) - Hash;
}

void update(int o,int L,int R){
    if(L == R) {
        sum[o]++;
        return;
    }
    int M = L + R >> 1;
    if(x <= M) update(o<<1,L,M);
    else update(o<<1|1,M+1,R);
    sum[o] = sum[o<<1] + sum[o<<1|1];
}

void query(int o,int L,int R){
    if(L == R) {
        tmp += sum[o];
        return;
    }
    int M = L + R >> 1;
    if(x <= M) {
    tmp += sum[o<<1|1];
    query(o<<1,L,M);
    }
    else query(o<<1|1,M+1,R);
}

inline void solve()
{
    top--; 
    x = lower_bound(Hash+1,Hash+top+1,0) - Hash;
    update(1,1,top);
    for(int i = 1;i <= n;i++)
    {
        a += data[i];
        x = lower_bound(Hash+1,Hash+top+1,a-t+1) - Hash;
        if(x > top){x = lower_bound(Hash+1,Hash+top+1,a) - Hash;update(1,1,top);continue;}
        tmp = 0;query(1,1,top);
        ans += tmp;
        x = lower_bound(Hash+1,Hash+top+1,a) - Hash;
        update(1,1,top);
    }
}

int main()
{
    init();
    solve();
    printf("%lld\n",ans);
    return 0;
}