Hello 2018

这场又没打，那就快点补回来吧

A.B

签到

C.Party Lemonade

题意

给两个数n，k，依次给出n种饮料的体积，每种为2^i(i=0,1,2,3.........)，费用为c[i]，问你要想得到k体积饮料，问最小花费

分析

首先题目很有特点，每种都为2^i，所有体积之间具有确定性的关系，从前往后贪心的为2^i取最优，贪心的取就可以了，不能整份取，将所有的情况考虑下即可

简单证明下：首先我们是从小的大的贪心，所以大的一定是当前最优的

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

int main() 
{
  int n, L;
  scanf("%d %d", &n, &L);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  for (int i = 0; i < n - 1; i++) {
    c[i + 1] = min(c[i + 1], 2 * c[i]);
  }
  long long ans = (long long) 4e18;
  long long sum = 0;
  for (int i = n - 1; i >= 0; i--) {
    int need = L / (1 << i);
    sum += (long long) need * c[i];
    L -= need << i;
    ans = min(ans, sum + (L > 0) * c[i]);
  }
  cout << ans << endl;
  return 0;
}

View Code

D. Too Easy Problems

题意

给n个问题，T秒时间，再给出n个问题，每个问题有a[i]（完成的完成数不能超过的数量），t[i]（完成这个问你所花的时间），问最多能完成的问题，输出这些问题的编号

分析

思路很简单啊，二分最大可以完成的问题数，check（mid）即可，check方法：对所有问题按照a[i]排序，大于mid的在对t[i]排序，看是否小于等于T即可

#include<cstdio>
#include<algorithm>
#define N 220000
using namespace std;
int n,T,a[N],t[N],q[N];
struct node{
    int id,t;
}qq[N];
bool cmp(node a,node b){return a.t<b.t;}
bool check(int mid){
    int num=0;
    for (int i=1;i<=n;++i) if(a[i]>=mid) q[++num]=t[i];
    sort(q+1,q+num+1);int x=0;if(num<mid) return 0;int time=0;
    for (int i=1;i<=num;++i){
        if(time+q[i]>T) break;
        ++x;time+=q[i];if (x>=mid) return 1;
    }return x>=mid;
}
int main()
{
    scanf("%d%d",&n,&T);
    for (int i=1;i<=n;++i) scanf("%d%d",&a[i],&t[i]);
    int l=0,r=n;
    while(l<=r){
        int mid=l+r>>1;
        if (check(mid)) l=mid+1;else r=mid-1;
    }printf("%d
",r);printf("%d
",r);int num=0;
    for (int i=1;i<=n;++i) if (a[i]>=r) qq[++num].t=t[i],qq[num].id=i;
    sort(qq+1,qq+num+1,cmp);for (int i=1;i<=r;++i) printf("%d ",qq[i].id);
    return 0;
}

View Code

E. Logical Expression

题意