家庭作业

#include<bits/stdc++.h>
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
typedef pair<int,int> PII;
ll n;
const int N = 1e6+10;
struct homework
{
    ll ddl,point;
    bool operator<(const homework& w)const//先修大学分
    {
        return point>w.point;
    }
}homeworks[N];
bool vis[N];//这天要做神魔作业
ll ans;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&homeworks[i].ddl,&homeworks[i].point);
    }
    sort(homeworks+1,homeworks+1+n);
    ll sign=0;//最小坑位
    for(int i=1;i<=n;i++)
    {
        if(homeworks[i].ddl <= sign)continue;//这坑没法占了，这学分不要也罢
        
        int j;
        for(j=homeworks[i].ddl;j>=1;j--)//从大的ddl开始寻找一个可以占的坑位
        {
            if(vis[j] == 0)
            {
                vis[j]=1;
                ans+=homeworks[i].point;
                break;//占到坑了
            }
        }
        if(j == 0)//没坑位了，说明前面的都已经给占了，而且已经是最优解了
        {
            sign=max(sign,homeworks[i].ddl);
        }
    }
    cout<<ans<<endl;
    return 0;
}

智力大冲浪

#include<bits/stdc++.h>
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
const int N = 510;
struct Game
{
    ll ddl,punishmoney;
    bool operator<(const Game& w)const
    {
        
        return punishmoney>w.punishmoney;
    }
}Games[N];
bool vis[10010];
ll m,n;
// 4
int main()
{
    cin>>m>>n;
    
    for(int i=1;i<=n;i++)cin>>Games[i].ddl;
    
    for(int i=1;i<=n;i++)cin>>Games[i].punishmoney;
    
    sort(Games+1,Games+1+n);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=Games[i].ddl;j>=1;j--)
        {
            if(vis[j] == 0)//每个点的游戏
            {
                vis[j]=1;
                Games[i].punishmoney=0;
                break;
            }
        }
    }
    ll punishfinal=0;
    for(int i=1;i<=n;i++)
    {
        punishfinal+=Games[i].punishmoney;
    }
    cout<<m-punishfinal<<endl;
    return 0;
}