Comment

lyt12345: 2024-12-18 16:05:20

将数据按价值排序，贪心的从大到小处理，每次尽量让作业拖到最后完成，如果和其他作业冲突就往前找，找到一个空闲的时间点。
注意此时问题的关键在于如何维护这个空闲时间数组。
考虑用树状数组进行维护。
设空闲时间数组C[i],第i个时间被占用则标记为1，空闲则为0.
如果单纯的用线性探查往回找，遇到0结束，这样不免有些笨拙。
我们多开一个树状数组b，b[i]记录的是以i结束的前lowbit(i)时间内的作业数量，如果b[i]==lowbit(i)则这个时间段满了，往回跳lowbit(i)继续找；如果不满，则判断当前c[i]是否为0，是则置1并对b进行维护，否则往前退1，开始下一轮判断。
树状数组的维护代价是log级别，非常强大。


排序复杂度O(n*logn),贪心复杂度为O(n*logn)，总复杂度在O(n*logn)级别，但空间开销多了一个树状数组，典型的以空间换时间。
附上代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;


struct node
{
	int lim;
	int v;
	bool operator < (const node &b)const{
		return v>b.v;
	}
};

node a[50004];
int b[50004],c[50004];

int lowbit(int x){return x&(-x);}

bool add(int x)
{
	int loc=-1;
	for(int i=x;i>0;)
	{
		if(b[i]==lowbit(i))i-=lowbit(i);
		else
		{
			if(c[i]==0){loc=i;break;}
			i--;
		}
	}
	if(loc==-1)return false;
	for(int i=loc;i<=50000;i+=lowbit(i))b[i]++;
	c[loc]=1;
	return true;
}

int main()
{
    int T;

    cin>>T;
    while(T--)
    {
		int n,i;
		cin>>n;

		for(i=0;i<n;i++)cin>>a[i].lim>>a[i].v;
		sort(a,a+n);

		long long int ans=0;

		memset(b,0,sizeof b);
		memset(c,0,sizeof c);
		for(i=0;i<n;i++)
		{
			int r=a[i].lim;
			if(add(r))
			ans+=a[i].v;
		}
		cout<<ans<<endl;
    }
}

Westbrook: 2024-05-31 11:38:57

一开始想用二分去查找能装入的时间段，然后发现其实也没必要，从大到小枚举就行，但从时间复杂度角度好像不能过，但是可能样例能过，然后别忘记答案要用long long不然就过不了：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 50000;
bool range[N];//表示该时间是否已经分配
struct Homework
{
    int d, p;//d指截止时间，p指作业收益
    bool operator<(const Homework& M)
    {
        return p > M.p;
    }
}h[N];

int main()
{
    int m;
    cin >> m;
    while (m--)
    {
        memset(range, false, sizeof range);
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int d, p;
            cin >> d >> p;
            h[i] = { d,p };
        }
        sort(h+1, h + n+1);
        long long int ans = 0;
        for (int i = 1; i<=n; i++)
        {
            //首先判断当前最大截止时间能否容纳该作业
            if (range[h[i].d] == false)//当前最大截止时间段没被容纳
            {
                range[h[i].d] = true;
                ans += h[i].p;
            }
            else
            {//当前最大截止时间被占领了
                for (int j = h[i].d; j >= 1; j--)
                {
                    if (range[j] == false)
                    {
                        range[j] = true;
                        ans += h[i].p;
                        break;
                    }
                }

            }
     
        }
        cout << ans << endl;
    }
    return 0;
}

hanser414627925: 2024-05-29 15:28:13

//贪心算法
#include<iostream>
using namespace std;
void QuickSort(long long*, long long* ,int, int);
void Swap(long long&, long long&);
bool isOK(int);
int	*t;
int main()
{
	int m, n;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int x, max = 0;
		long long mon = 0;
		cin >> n;
		long long* d = new long long[n], * p = new long long[n];
		for (x = 0; x < n; x++)
		{
			cin >> d[x] >> p[x];
			if ((int)d[x] > max)max = (int)d[x]; //截止时间di
		}
		QuickSort(p,d, 0, n - 1);	//按照作业利益pi大小从小到大排列
		t = new int[max+1];
		for (x = 0; x < max + 1; x++)
			t[x] = 0;
		for (int k = n-1; k >=0; k--)	//N个作业
		{
			if (isOK((int)d[k]))mon += p[k];
		}
		cout <<mon << endl;
	}
	return 0;
}
bool isOK(int d)
{
	for (int i = d; i >= 1; i--)
		if (t[i] == 0) { t[i] = 1; return true; }
	return false;
}
void QuickSort(long long* a, long long*b ,int x, int y)
{
	if (x >= y)return;
	int pivot = a[x], pivotpos = x;
	for (int i = x; i <= y; i++)
	{
		if (a[i] < pivot)
		{
			pivotpos++;
			if (pivotpos != i)			//小于基准的交换到左侧
			{
				Swap(a[pivotpos], a[i]);
				Swap(b[pivotpos], b[i]);
			}
		}
	}
	Swap(a[x], a[pivotpos]);
	Swap(b[x], b[pivotpos]);
	QuickSort(a, b,x, pivotpos - 1);
	QuickSort(a,b, pivotpos + 1, y);
}
void Swap(long long& x, long long& y)
{
	long long temp = x;
	x = y;
	y = temp;
}

RobinLi: 2024-05-24 10:17:59

楼上的对时间槽的定义似乎有问题诶，时间槽slot的数量应该为N，而不是（maxDeadline + 1）。
话说是十二月份也有算法课吗，为啥我看到有冬天写OJ的哈哈哈

chenyi6呀: 2023-12-06 14:48:56

为什么这样无法通过呢？求大佬帮忙看看
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Job{
    int ddl;
    int p;
};

bool compare(Job a, Job b){
    return a.p > b.p;
};

int main() {
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<Job> jobs(n);
        int maxDeadline = 0;

        for(int i = 0; i < n; i++) {
            cin >> jobs[i].ddl >> jobs[i].p;
            maxDeadline = max(maxDeadline, jobs[i].ddl);
        }

        // 对工作进行排序，收益越大越排在前面
        sort(jobs.begin(), jobs.end(), compare);

        vector<bool> slots(maxDeadline + 1, false);  // 时间槽，初始化为未占用
        long long res = 0;  // 总收益

        for(int i = 0; i < n; i++) {
            for(int j = jobs[i].ddl; j > 0; j--) {
                // 找到一个未被占用的时间槽
                if(!slots[j]) {
                    slots[j] = true;  // 标记时间槽被占用
                    res += jobs[i].p;  // 累加收益
                    break;
                }
            }
        }

        cout << res << endl;
    }
    return 0;
}

神明的迷思: 2023-06-08 16:15:34

感谢楼上老哥，我用int报错，改为long long后成功提交了

kokoro: 2022-11-07 10:21:44

不用long long就是报错，WA、CE、TLE有可能

Destiny_Violet: 2021-06-16 09:10:47

我吐了，真的得long long,没有一点提示啊

uranium: 2021-05-20 17:04:40

CE is because there're chinese characters

09019105王璟: 2021-05-09 02:00:29

为什么会编译错误啊，我要吐了啊@！！求大佬帮忙看看




/*思路：贪心
按效益从大到小把作业排序, 选中的作业放在集合J
依次判断作业（最大收益优先选中）:ddl未被占用则在ddl的时候做这份作业。（最大收益尽可能迟完成）
如果ddl等于任何已选中作业的ddl，则看看能不能早点完成，往前找空闲时间段即J[i]==0（hash线性探测法）
ddl之前的时间段都被占用就不加入J
*/
//实际上没有集合J，我只要总价值
//如何判断给定的时间单元段是否被作业占用->关键字时间单元是否存在->vector查找find_if即可

#include<iostream>
#include<algorithm>
using namespace std;
struct job
{
	int ddl; int pi;
};

bool operator>(job a, job b)
{
	return a.pi < b.pi;
};
bool operator<(job a, job b)
{
	return a.pi > b.pi;
};
template<typename T>
void merge_sort(T arr[], int len) {省略}
long long int getPi(job* arr,int size)//获得最大收益
{
	long long int p = 0; int *times = new int[50000]; memset(times, 0,200000);
	merge_sort(arr,size);//按收益降序排作业数组arr
	//for (int i = 0; i < size; i++)cout << arr[i].pi << " ";
	p += arr[0].pi; times[arr[0].ddl] = 1;
	for (int i = 1; i < size; i++)
	{
		//arr[i].ddl在时间数组中不存在，则时间数组插入ddl,p+= arr[i].pi;
		//否则arr[i].ddl在时间数组中找最迟的不存在的比它小的ddl’,时间数组插入ddl',p+= arr[i].pi;
		//否则不操作
		for (int k = arr[i].ddl;k>0; k--)
		{
			if (times[k] == 0)
			{
				times[k] = 1; //cout << " 新pi" << arr[i].pi<<" ";
				p += arr[i].pi; break;
			};
		};
	}; delete[] times;
	return p;
};

int main()
{
	int T, N;
	cin >> T;
	while (T--)
	{
		cin >> N;
		job* arr = new job[N];
		for (int i = 0; i < N; i++)
			cin >> arr[i].ddl >> arr[i].pi;
		cout << getPi(arr, N) << endl; delete[] arr;
	};	
}

_heye_: 2021-03-31 10:41:28

这是什么玄学玩意 改为64位就行了

LMxKc1998831: 2020-12-24 20:20:48

卡我两天，我吐了哈哈哈哈

zhang2020: 2020-12-20 20:19:20

感谢楼上的楼上的老哥， 我直接好家伙

mxkkkk: 2020-12-20 19:51:10

感谢楼上的楼上的老哥， 我直接好家伙

Lixinwei: 2020-11-29 16:45:08

感谢楼上老哥， 我直接好家伙

200818倪鹏宇: 2020-11-14 23:41:19

结果要用64位存TAT