題目鏈接
http://codeforces.com/problemset/gymProblem/100703/I
Description
standard input/outputAs a matter of fact, Dragon knows what Prince is interested in now. Prince uses to spend his rare off days learning different courses and trainings. But Dragon doubts whether he should tell Princess about it.
Prince decided that he needs some extra knowledge and skills. He chose n fields in which he wanted to gain knowledge and skills most of all. After this, he learned that m1, m2, ..., mn courses and trainings of each of fields exist.
Prince took a close look at descriptions of courses and trainings and drew a table, in which sij is a value by which ith skill is increased after studying jth course (j = 1, 2, ..., mi).
Prince believes that his basic knowledge and skills in all these fields are negligible, so they can be considered zero. He wants to evolve his knowledge and skills harmonically. In his opinion, he will reach the greatest harmony if he chooses one course for each field in such a way that difference between the highest and the lowest their increases would be as minimum as possible.
Your task is to find the courses which Prince should choose.
Input
The first line contains integer n (1 ≤ n ≤ 200) — the number of fields which Prince is interested in.
The second line contains n integers m1, m2, ..., mn (1 ≤ mj ≤ 1000, j = 1, 2, ..., n) — the number of courses for each of fields.
The next n lines contain values sij (1 ≤ sij ≤ 109) — knowledges and skills, which Prince would gain at the courses. The first of thesen lines contains values s11, s12, ..., s1m1, the second — values s21, s22, ..., s2m2, etc.
The values sij are listed in the numerical order of courses for each of the fields.
Output
In the first line print one integer — minimum difference between the highest and the lowest numbers of increase.
In the second line print n integers — numbers of courses which Prince should choose. List the numbers in the same order in which the fields are listed.
If there is more than one answer — choose any of them.
Sample Input
Input2Output
2 3
4 3
3 1 2
0Input
2 1
4Output
3 5 4 5
8 7 15
3 10 4 8 5
4 4 4 5
1 2 12 8 9
3
2 5 4 4
題意：輸入一個n，然後輸入n個數，表示接下來輸入的n行每行的數的個數，求在每行中選擇一個數使得這n個數的最大值與最小值的差最小，輸出最小的差值和每行選擇的數的列號；
思路：尺取，將n行的數放在一起從小到大排序，定義s=0和e=0，表示s~e的一段區間，e向右移動，直到這個區間包含n行的數，那麼node[e].x-node[s].x便是從這個區間選擇的n行數的最小差值，然後s++，再讓e右移，計算區間n行數最小差值......
代碼如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
const int M=1e9+5;
const int maxn=2e5+5;
int A[205],cnt[205],vis[205];
struct Node
{
int x,h,l;
}node[maxn],ans[205];
bool cmp1(const Node s1,const Node s2)
{
return s1.x<s2.x;
}
bool cmp2(const Node s1,const Node s2)
{
return s1.h<s2.h;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
scanf("%d",&A[i]);
int tot=0;
for(int i=0;i<n;i++)
for(int j=1;j<=A[i];j++)
{
scanf("%d",&node[tot].x);
node[tot].h=i;
node[tot++].l=j;
}
sort(node,node+tot,cmp1);
int tmp=M,s=0,e=0,sum=0;
int pos1,pos2;
while(1)
{
while(e<tot&&sum<n){
cnt[node[e].h]++;
if(cnt[node[e].h]==1) sum++;
e++;
}
if(sum<n) break;
if(node[e-1].x-node[s].x<tmp){
tmp=node[e-1].x-node[s].x;
pos1=s;
pos2=e-1;
}
if(tmp==0) break;
if(cnt[node[s].h]==1) sum--;
cnt[node[s].h]--;
s++;
}
int p=0;
for(int i=pos1;i<=pos2;i++)
{
if(vis[node[i].h]==0)
{
vis[node[i].h]=1;
ans[p].h=node[i].h;
ans[p++].l=node[i].l;
}
}
sort(ans,ans+n,cmp2);
printf("%d\n",tmp);
for(int i=0;i<n;i++)
printf("%d%c",ans[i].l,(i+1==n)?'\n':' ');
}
return 0;
}
