poj1752 Advertisement(差分约束:输出路径 | 贪心:区间选点)-爱代码爱编程
题意:广告商在跑步者门的沿途中插播广告,为了节约资金,现在尽量少的插播广告。已知每个跑步者跑步路标的起点和终点,如果之间路标的个数小于k,那么必须是在每个路标上都有广告,否则,沿途是k个。题意让你求最少需要多少个广告位,然后让你输出一种可能。
思路:这是个区间前缀模型的差分约束。不过需要输出最长路的路径。对于每个节点如果d[i] - d[i - 1] == 1,那么 i 就是最长路上的一个点。
AC Code:
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstdio>
#include<sstream>
#include<vector>
#include<algorithm>
using namespace std;
#define read(x) scanf("%d",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define gc(x) scanf(" %c",&x);
#define mmt(x,y) memset(x,y,sizeof x)
#define write(x) printf("%d\n",x)
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
#define mod 998244353
const int N = 1e5 + 10;
const int M = 1e5 + 1005;
int off = 10001;
int d[N];bool vis[N];
struct Edge
{
int next;
int to;
int dis;
}edge[M];
int head[N],tot;
inline void add(int from,int to,int dis){
edge[++tot].next = head[from];
edge[tot].to = to;
edge[tot].dis = dis;
head[from] = tot;
}
void spfa(int u)
{
mmt(d,0xcf);
mmt(vis,0);
queue<int> Q;
d[u] = 0;
Q.push(u);
vis[u] = 1;
while(Q.size()){
int x = Q.front();
Q.pop();
vis[x] = 0;
for(int i = head[x];~i;i = edge[i].next){
int y = edge[i].to;
int dis = edge[i].dis;
if(d[y] < d[x] + dis){
d[y] = d[x] + dis;
if(!vis[y]){
Q.push(y);
vis[y] = 1;
}
}
}
}
}
void init()
{
mmt(head,-1);
tot = 0;
}
int main()
{
int k,m;
while(~scanf("%d%d",&k,&m)){
init();
int u,v;
int s = INF,t = -INF;
for(int i = 1;i <= m;++i){
Read(u,v);
if(u > v) swap(u,v);
u += off;v += off;
s = min(s,u - 1);t = max(t,v);
if(v - u < k){
add(u - 1,v ,v - u + 1);
add(v,u - 1,-(v - u +1));
}
else add(u - 1,v,k);
}
for(int i = s;i < t;++i){
add(i ,i +1,0);
add(i +1,i , - 1);
}
spfa(s);
int sum = 0;
for(int i = s;i <= t;++i){
if(d[i] - d[i-1] == 1) sum++;
}
cout<<sum<<endl;
for(int i = s;i <= t;++i){
if(d[i] - d[i -1 ] == 1) cout<<i - off<<endl;
}
}
}
看了这位的文章才发现,这不就是个赤裸裸区间选点的贪心吗。
先按区间右端点从小到大排序,右端点相同的情况下按左端点从大到小排序。然后每次尽可能靠右选点。
AC Code:
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstdio>
#include<sstream>
#include<vector>
#include<algorithm>
using namespace std;
#define read(x) scanf("%d",&x)
#define Read(x,y) scanf("%d%d",&x,&y)
#define gc(x) scanf(" %c",&x);
#define mmt(x,y) memset(x,y,sizeof x)
#define write(x) printf("%d\n",x)
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
#define mod 998244353
const int N = 1e5 + 10;
const int maxn = 1e5 + 1005;
struct node{
int x,y;
bool operator <(node A)const{
if(y != A.y) return y < A.y;
else return x > A.x;
}
}ans[1010];
int off = 20010;
bool vis[40000];
void init()
{
mmt(vis,0);
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
init();
int u,v;
int s = INF,t = -INF;
for(int i = 1;i <= m;++i){
Read(u,v);
if(u > v) swap(u,v);
u += off,v += off;
s = min(s,u);t = max(t,v);
ans[i].x = u,ans[i].y = v;
}
sort(ans + 1,ans + m + 1);
int sum = 0;
for(int i = 1;i <= m;++i){
if(ans[i].y - ans[i].x + 1<n){
for(int j = ans[i].x;j <= ans[i].y;++j){if(!vis[j])sum++,vis[j] = 1;}
}
else {
int cnt = 0;
for(int j = ans[i].x;j <= ans[i].y;++j){
if(vis[j]) cnt ++;
}
if(cnt >=n) continue;
cnt = n - cnt;
for(int j = ans[i].y;j >= ans[i].x;--j){
if(cnt == 0) break;
if(!vis[j]) vis[j] = 1,cnt--,sum ++;
}
}
}
cout<<sum<<endl;
for(int i = s;i <= t ;++i){
if(vis[i]){
cout<<i - off<<endl;
}
}
}
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/qq_43408238/article/details/103153037