FatMouse's Speed——J
J. FatMouse's Speed
Input
The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.
Two mice may have the same weight, the same speed, or even the same weight and speed.
Output
W[m[1]] < W[m[2]] < ... < W[m[n]]
and
S[m[1]] > S[m[2]] > ... > S[m[n]]
In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.
Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
Sample Output
4
4
5
9
7
题意:
要求找到的体重递增,速度递减的老鼠,并且输出最长的长度数,而且输出各自的序列数。(Special Judge 说明答案不唯一,只要输出的答案正确就可以)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int num,w,s;
}a[];
int cmp(node c,node d) {return c.w<d.w;}
int x,y,k,t[],r[];
int main()
{
int i,j,L,p=,ant=,er=;
k=;
memset(t,,sizeof(t));
while(cin>>x>>y)
{
a[k].num=k+;
a[k].w=x;
a[k].s=y;
k++;
}
sort(a,a+k,cmp);
for(i=;i<k;i++) t[i]=;
for(i=;i<k;i++)
{
for(j=;j<i;j++)
{
if(a[j].s>a[i].s&&a[j].w<a[i].w&&t[i]<t[j]+)
t[i]+=;
}
}
for(i=;i<k;i++) p=max(p,t[i]);
cout<<p<<endl;
for(i=;i<k;i++)
{
if(p==t[i]) j=i;
}
int temp=j;
r[er++]=a[j].num;
for(L=j-;L>=;L--)
{
if(t[L]+==t[j]&&a[L].s>a[temp].s)
{
ant++;
r[er++]=a[L].num;
t[j]=t[L];
temp=L;
}
if(ant==p) break;
}
for(i=er-;i>;i--) cout<<r[i]<<endl;
return ;
}
最新文章
- PHP两种基础的算法:冒泡、快速排序法》》》望能够帮助到大家
- 先装.net后装iis的问题
- java文件保存至服务器
- oracel数据泵的使用
- python 操作注册表
- UVA1025---A Spy in the Metro(DP)
- struct和union分析实例
- oracle 存储过程基础
- 用标准C编写COM(一)
- LINUX启动ORACLE监听和服务
- NET中级课--文件,流,序列化2
- JAVA: httpclient 具体解释——第五章;
- 【JMeter】source(";文件路程";)和${变量}同时出现会报错
- shell脚本中单双引号疑惑
- 斐讯 天天牛绑定教程 邀请码:8vozbf
- 验证对Random的两个猜想
- QString 与 string转换
- HTML5+CSS把footer固定在底部
- nGrinder的安装与使用
- iftop、ifstat详解