贪心策略：
在不过期的时间内优先卖出利润更大的产品。
按照价值降序，每次扫描到一个价值，尝试一下在过期之前能不能卖出去；此时可能已经有比它更大价值的产品占用了一些日期，于是从过期时间往前面找，直到找到一个空位置。如果这个空位置大于0，那么就把这个产品安排在这天卖出。
暴力找位置最坏复杂度可以达到$O(n^2)$，所以用并查集优化，每个节点代表日期，日期记录他最近的前面的空闲日期是哪天，每次用掉这天就把这个点和前面的点连起来
实测比优先队列快了三倍
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 233;
typedef pair<int,int> pii;
vector<pii> a;
int f[maxn];
int ff(int x)
{
if(f[x] == x) return x;
return f[x] = ff(f[x]);
}
int main()
{
int n;
while(cin >> n)
{
int ans = 0;
a.clear();
int maxe = 0;
for(int i = 1; i <= n; i++)
{
int v,e;
scanf("%d%d", &v, &e);
a.push_back({-v, e});
maxe = max(maxe, e);
}
for(int i = 0; i <= maxe; i++) f[i] = i;
sort(a.begin(), a.end());
for(int i = 0; i < a.size(); i++)
{
int v = -a[i].first, e = a[i].second;
int pos = ff(e);
if(pos > 0)
{
ans += v;
f[pos] = pos - 1;
}
}
printf("%d\n", ans);
}
}
妙极了
秒啊妙啊
这段代码有无讲一下
for(int i = 0; i < a.size(); i++)
{
int v = -a[i].first, e = a[i].second;
int pos = ff(e);
if(pos > 0)
{
ans += v;
f[pos] = pos - 1;
}
}
pos找的就是前e天哪天有可能空闲。 如果找到的那天还大于零天（小于等于零天无意义），那就把这天用掉，然后把这天加入到 pos - 1 为fa的集合。（如果这个fa的这天也被用掉，会一直往前找，只到找到哪天没有被用）
请问一下我这个程序哪错了，实在是找不出来。
样例过了，但提交后错了。
#include<bits/stdc++.h> using namespace std; int a[10001],b[10001]; vector<int>g[10001]; int main() { int n,mmax=0; while(cin>>n) { for(int i=1; i<=n; ++i) { cin>>a[i]>>b[i]; g[b[i]].push_back(a[i]); } int x=0,ans=0; for(int i=1; i<=10001; ++i) { if(g[i].size()) { for(int j=0; j<g[i].size(); ++j) { x=max(x,g[i][j]); } ans+=x; } x=0; } cout<<ans<<endl; memset(g,0,sizeof(g)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); } }初次发，不知道咋弄好，请见谅
测了一下根堆33ms, 楼主的并查集51ms…
少女啊
f[pos] = pos - 1 ? 为甚吗不是 f[pos] = f[pos] - 1 ??
我也感觉是f[pos] - 1
试了一下，都可以的
因为被插入的位置一定是空位置，即是一个父节点，满足f[pos] = pos。
因此f[pos] = pos - 1 和 f[pos] = f[pos] - 1 是等价的。
为什么不是f[pos]=ff(pos-1)
我感觉也是
妙啊
妙啊