给你一个长度为$N$的整数序列$Xi$，请判断是否存在一个满足下列条件的整数序列$a$，如果存在，请构造一种方案
条件如下：
- $a$的长度为$N^2$，并且满足数字$1,2,3…N$都各出现恰好$N$次
- 对于$1 le i le N$，数字$i$在$a$中第$i$次出现的位置是$X_i$
$1 le N le 500, ;1le X_ile N^2$，保证$X_i$互不相同
Solution
转化一下问题。题目相当于对于每个$i$，规定在$[1,x_i)$要放$i-1$个$i$，在$(x_i,n^2]$要放$n-i$个$i$
我们称前者为“向前”的请求，后者为“向后”的请求
这样，我们就得到了$2n$个有范围和次数限制的请求。我们可以将它们看做各自独立的请求。
考虑从左往右枚举每一个位置$p=1…n^2$，并确定当前位置应该用来填入哪一个请求（或者说对其贡献）
首先，观察考虑对象的变化：当前位置右移时，能填入的向前请求越来越少，而能填入的向后请求越来越多
假设我们对于当前可用的向前的请求，按其结束位置（右端点$x_i-1$）从小到大排序，显然当前位置$p$应该填入结束位置最靠左的那一个请求，记其为$A$；如果$p$填入的请求不是$A$，而是结束位置更靠右的请求，我们完全可以填入$A$，且情况一定不会更劣，因为我们从左到右填时，优先填入了那些剩余周旋空间更小的请求
那么我们的策略就是：如果当前有可用的向前请求，将当前位置填入结束位置最靠左的那一个。如果填完后该请求已满，则删去这个请求。
当前位置右移时，弹出的显然是结束位置最靠左的请求，如果此时其还未被满足，则无解
那么向后请求怎么办呢？我们发现，在考虑向前请求时之所以要优先分配给最靠左的请求，是因为最靠左的元素在最近的将来就要失去考虑机会；而对于向后的请求，随着枚举位置的右移，机会反而越来越多。因此，我们就不需要给向后请求太多的关照。当且仅当没有向前请求时，我们再随便给一个当前可考虑的向后请求填入$p$即可
整体算法可以用一个数组和界限指针模拟
Summary
感觉无法很好地设置状态、刻画阶段的题目，有可能就是贪心了
线性贪心，一般是从左往右扫，优先考虑、调配和满足那些所剩考虑余地更小的元素（隐形前提是，这些考虑余地和从左往右扫呈线性相关）
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <algorithm>
#define END {puts("No"); return 0;}
using namespace std;
const int N=510;
int n;
int a[N];
int who[N];
int ans[N*N];
struct {
int id,rest;
}s1[N*N],s2[N*N];
int s1cnt,s2cnt;
void readData(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ans[a[i]]=i;
}
}
bool cmpByA(const int &u,const int &v){
return a[u]<a[v];
}
bool init(){
for(int i=1;i<=n;i++) who[i]=i;
sort(who+1,who+1+n,cmpByA);
for(int i=1;i<=n;i++){
int x=who[i];
if(x-1>a[x]-1||n-x>(n*n)-a[x])
return false;
if(x>1)
s1[++s1cnt]=(Set){x,x-1};
if(x<n)
s2[++s2cnt]=(Set){x,n-x};
}
return true;
}
bool solve(){
int b1=1,b2=1,c1=1,c2=1;
int m=n*n;
for(int i=1;i<=m;i++)
if(!ans[i]){
while(c1<=s1cnt&&a[s1[c1].id]-1<i){
if(s1[c1].rest)
return false;
c1++;
}
while(b2<=s2cnt&&a[s2[b2].id]+1<=i)
b2++;
if(c1>s1cnt&&c2>=b2)
return false;
if(c1<=s1cnt){
ans[i]=s1[c1].id;
s1[c1].rest--;
if(!s1[c1].rest)
c1++;
}
else{
ans[i]=s2[c2].id;
s2[c2].rest--;
if(!s2[c2].rest)
c2++;
}
}
return true;
}
int main(){
readData();
if(!init())
END;
if(!solve())
END;
puts("Yes");
for(int i=1;i<=n*n;i++) printf("%d ",ans[i]);
return 0;
}
|
近期评论