学步园

题目链接：http://codeforces.com/problemset/problem/3/B

问题的意思很是简单，n( n <= 10^5)件物品，每件体积为1 或者 2， 每件有一个价值v(10^4)。

问，对于背包容量为V(V <= 10^9)的背包，可以装的最大价值。还要输出都装来了哪些件，并输出其编号。。

咋一看挺像背包的。。但是， 由于需要输出都装了哪些个件，也就是需要输出路径。比较麻烦。。

由于物品的体积只有1 或者 2。。所以还是比较好搞的。。贪心搞之。。

我的贪心策略。。

1.按单位价值排序。。

2.从单位价值一件一件来装。

3.特判最后如果还有一个单位的体积，把装入的体积为1的最小价值的物品拿出来，放入没有装入的体积为2的最大价值的物品装进去。。

这样就ok了。。

Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <stack>
using namespace std;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct Boat
{
    int type;
    int v;
    int tv;
    int id;
}b[N];

bool vis[N];
bool cmp(Boat a, Boat b)
{
    if(a.tv > b.tv) return true;
    else if(a.tv == b.tv && a.type > b.type) return true;
    return false;
}
int n, V;
int ans[N], top;
int maxv;
bool cmp1(Boat a, Boat b)
{
    if(a.id < b.id) return true;
    return false;
}

void f()
{
    sort(b + 1, b + 1 + n, cmp1);
    int minn = INF, iid = -1;
    for(int i = 0; i < top; i ++){
        if(b[ans[i]].type == 1 && b[ans[i]].v < minn){
            iid = ans[i]; minn = b[ans[i]].v;
        }
    }
    if(iid == -1) return ;
    int maxx = -1, iiid = -1;
    for(int i = 1; i <= n; i ++){
        if(!vis[i] && b[i].type == 2 && b[i].v > maxx){
            iiid = i; maxx = b[i].v;
        }
    }
    if(iiid == -1) return ;
    vis[iid] = false; vis[iiid] = true;
    maxv -= b[iid].v; maxv += b[iiid].v;
    ans[top ++] = iiid;
}

int main()
{
//    freopen("1.txt", "r", stdin);
    memset(vis, 0, sizeof(vis));
    cin >> n >> V;
    for(int i = 1; i <= n; i ++){
        int tt, vv;
        cin >> tt >> vv;
        b[i].type = tt;
        b[i].v = vv;
        b[i].tv = (tt == 1 ?  2 * vv : vv);
        b[i].id = i;
    }
    sort(b + 1, b + 1 + n, cmp);
    top = 0; maxv = 0;
    for(int i = 1; i <= n && V > 0; i ++){
        if(V >= 2){
            ans[top ++] = b[i].id;
            vis[b[i].id] = true;
            maxv += b[i].v;
            V = V - b[i].type;
        }
        else {
            if(b[i].type == 1){
                maxv += b[i].v;
                ans[top ++] = b[i].id;
                vis[b[i].id] = true;
                V = 0;
                break;
            }
        }
    }
    if(V) f();
    cout << maxv << endl;
    if(maxv == 0){
        return 0;
    }
    queue<int> st;
    for(int i = 1; i <= n; i ++){
        if(vis[i]) st.push(i);
    }
    printf("%d", st.front());
    st.pop();
    while(!st.empty()){
        printf(" %d", st.front());
        st.pop();
    }
    return 0;
}

水水贪心，但是，自己最后也没有a了。。仍然需要努力学习。。